\(n\) 桁の数 \(2\ldots 2\) は、\(\frac{2}{9}(10^n-1)\) と表すことができます。したがって問題は「\(M\) が与えられたとき、\(\frac{2}{9}(10^n-1) \equiv 0 \bmod M\) を満たす最小の \(n\geq 1\) を求めよ」と読み替えられます。

一般に、

• \(ax\equiv 0 \bmod M \Longleftrightarrow x\equiv 0 \bmod \frac{M}{\gcd(M,a)}\)
• \(\frac{x}{b}\)が整数 かつ \(\frac{x}{b} \equiv 0 \bmod M \Longleftrightarrow x\equiv 0\bmod bM\)

が成り立つことから、この問題はさらに

「\( 10^n\equiv 1 \bmod M'\) を満たす最小の \(n\geq 1\) を求めよ。ただし、\(M'\) は、\(M\) が偶数のとき \(\frac{9M}{2}\)、\(M\) が奇数のとき \(9M\) とする」と読み替えられます。

この問題は、以下の \(2\) 通りのアプローチのいずれかにより解くことができます。

解の候補を絞り全探索する

オイラーの定理 から \(10^{\phi(M')}\equiv 1 \mod M'\) となるので、求めるべき最小の \(n\) は \(\phi(M')\) の約数となります。

なぜ？

背理法で示します。もし \(n\) が \(\phi(M')\) の約数でないと仮定すると、\(d=\gcd(n,\phi(M'))\) は \(n\) より小さくなります。さらに、\(an+b\phi(M')=d\) となる整数 \(a,b\) をとることができ、\(10^d\equiv (10^n)^a (10^{\phi(M')})^b\equiv 1 \bmod M'\) となり、\(n\) より小さな解 \(d\) が存在し矛盾します。

したがって、\(\phi(M')\) の約数を列挙し、小さい順に全て調べることで答えを求めることができます。\(\phi(M')\) の計算と \(\phi(M')\) の約数列挙はそれぞれ \(O(\sqrt{M'})\) で行えるため、全体で \(O(\sqrt{M'})\) で解くことができます。

実装例(C++)

離散対数問題として解く

「\(a,b,M\) が与えられたとき、\(a^x=b \mod M\) を満たす(最小の) \(x\) を求めよ」という問題は離散対数問題として知られており、Baby-step Giant-step と呼ばれるアルゴリズムを用いることで \(O(\sqrt{M} \log M)\) で解くことができます。hashmapなどを用いることで expected \(O(\sqrt{M})\) にもなります。

一般の離散対数問題では、\(\gcd(a,M)>1\) のケースに対する処理がやや複雑ですが、\(b=1\) である今回は必ず解なしになることが示せます。

実装例(C++)
実装例(Python)