ABC222G 222

解説なしAC

はレプユニット数という呼ばれ、その一般項はなので、この問題の一般項はです。

2や9を無視できれば、を求める問題になり、フェルマーの小定理などで解けそうという感じなので、2と9をどうにかします。

とします。

Kに2を含む場合

XがKの倍数であるとは、XがKを因数として含んでいることと同義です。

Xの外に2があるので、Xが含む2は、Kより1つ少なくてもよく、Xはの倍数でよくなります。

よって、とします。

Kに3を含む場合

Kが3を因数に含む時、Xの外に÷9があるので、Xに含まれる3は2個まで打ち消されます。

よって、Xがもつ3は、Kより2つ多い必要があり、Xはの倍数である必要があります。

よって、とします。

を求める

ここまでの準備ができたら、実際にを求めます。

・10とKが互いに素

まず、K = 1のときは例外ケースで、答えは1です。

そうでない時、Kが素数ならフェルマーの小定理が使えますが、今回は素数とは限りません。

このような時、より一般化されたオイラーの定理が使えます。

正の整数について、互いに素であれば、

但し、関数はオイラーのトーシェント関数

しかし、は、1となる最小の正の整数とは限らないので、更に以下を利用します。

を満たす最小の正の整数nは、の約数である。

---------------------------------------------------------------------------

証明

は、整数で割った商と余りを用いて、と表せる。よって、

より、

はで割った余りであるので、であり、

仮定よりがを満たす最小の正の整数なので、となり、

であるため、はの約数である。

(参考:MATHEMATICS.PDFの巡回群のPDF)

-----------------------------------------------------------------------------

以上から、

・を求める()

・の約数のうち、を満たす最小のものを求める()

ことで、解を得られます。

・10とKが互いに素でない

オイラーの定理などは満たしません。

そこで、元の問題に立ち返ってみます。

Kは2と5いずれか、または両方を因数に含んでいます。

2を含んでいる場合、その倍数の一の位は0,2,4,6,8

5をを含んでいる場合、その倍数の一の位は0,5

2と5を含んでいる場合、その倍数の一の位は0

になりますが、考えている数列はすべての項の一の位が9となるため、Kの倍数となることはあり得ません。

よって、このケースでは答えは-1です。

提出コード：

https://atcoder.jp/contests/abc222/submissions/26542389

別途、公式解説の離散対数問題について解釈した記事を書いてみたいと思います。