スナネコです。twitterで出した問題について解説します。
問題その１：
高橋君は の倍数と 7 が好きです。
7,77,777,…という数列の中に初めて の倍数が登場するのは何項目ですか？
存在しない場合は代わりに -1 を出力してください。
制約：
解説：
が 7 の倍数のとき
、そうでないとき
とします。
次のように同値変形できます
- 77...77 (n桁)が
の倍数
- 11...11 (n桁)が
の倍数
- 99...99 (n桁)が
の倍数
よって、最後の式を満たす最小の を求めれば良いです。
解法１：離散対数問題
この問題は離散対数問題そのものなので、Baby-Step Giant-Stepなどを用いることで、 で解くことができます。
解法２：乗法群における位数
明らかに、 が2の倍数か5の倍数のときは答えが-1になることがわかります。
そうでないとき、オイラーの定理から、が成り立ちます。
なので、 を満たす最小の
は、
の約数となることがわかります。
（もしそうでなければ、として、より小さい答えが作れるので矛盾します）
を求め、素因数分解し、約数を全探索することで、
で解くことができます。
128bit整数がないとちょっと計算が大変ですね。
問題その２：
高橋君は の倍数と 7 が好きです。
7,77,777,…という数列の中に初めて の倍数が登場するのは何項目ですか？
の全ての
について求めてください。
存在しない場合は代わりに -1 を出力してください。
制約：
解説：
を満たす最小の
を
と書くことにします。
もし、 が互いに素なら、
を満たす最小の
は、中国剰余定理から
になることがわかります。
よって、素数べきに対する答えが求めることができれば、それらを組み合わせて一般の場合に答えることができます。
最初に 以下の数の最小素因子テーブルを作っておき、素因数分解が
で出来るようにしておきます。（osa_k法というやつですね）
素数 に対しての答えは、問題その１で説明した方法によって、
で求めることが出来ます。
証明は省略しますが、 は
か
になります。どちらになるかは実際に計算することで、
で確かめられます。
（証明は「」を二項定理を使って示します。ちなみに、
になるのは、
のときの 3, 487, 56598313 の3通りしか知られていないようです（A045616））
これらをうまく組み合わせると、全体で で解くことができます。
埋め込みで解けてしまうのと、との区別が難しいのとで、実際のコンテストに出すのは無理ですね。
