ABC174C Extra

スナネコです。twitterで出した問題について解説します。

問題その1:
高橋君は K の倍数と 7 が好きです。
7,77,777,…という数列の中に初めて K の倍数が登場するのは何項目ですか?
存在しない場合は代わりに -1 を出力してください。

制約:
K1012

解説:
K が 7 の倍数のときK=K/7、そうでないとき K=K とします。
次のように同値変形できます

  • 77...77 (n桁)が K の倍数
  • 11...11 (n桁)が K の倍数
  • 99...99 (n桁)が 9K の倍数
  • 10n=1mod9K

よって、最後の式を満たす最小の n を求めれば良いです。

解法1:離散対数問題
この問題は離散対数問題そのものなので、Baby-Step Giant-Stepなどを用いることで、O(KlogK) で解くことができます。

解法2:乗法群における位数
明らかに、K が2の倍数か5の倍数のときは答えが-1になることがわかります。
そうでないとき、オイラーの定理から、10ϕ(9K)=1mod9Kが成り立ちます。
なので、10n=1mod9K を満たす最小の n は、ϕ(9K) の約数となることがわかります。
(もしそうでなければ、n=gcd(n,ϕ(9K))として、より小さい答えが作れるので矛盾します)
ϕ(9K)を求め、素因数分解し、約数を全探索することで、O(K)で解くことができます。

128bit整数がないとちょっと計算が大変ですね。





問題その2:
高橋君は K の倍数と 7 が好きです。
7,77,777,…という数列の中に初めて K の倍数が登場するのは何項目ですか?
1KN の全ての K について求めてください。
存在しない場合は代わりに -1 を出力してください。

制約:
N106

解説:

10n=1modM を満たす最小の nf(M) と書くことにします。
もし、a,b が互いに素なら、10n=1modab を満たす最小の n は、中国剰余定理から lcm(f(a),f(b)) になることがわかります。
よって、素数べきに対する答えが求めることができれば、それらを組み合わせて一般の場合に答えることができます。
最初に 9N 以下の数の最小素因子テーブルを作っておき、素因数分解O(logN) で出来るようにしておきます。(osa_k法というやつですね)
素数 p に対しての答えは、問題その1で説明した方法によって、O(p-1の約数の個数×logN) で求めることが出来ます。
証明は省略しますが、f(pe)f(pe1)pf(pe1)になります。どちらになるかは実際に計算することで、O(logN) で確かめられます。
(証明は「f(pe)f(pe1)f(pe)=pf(pe1)」を二項定理を使って示します。ちなみに、f(pe)=f(pe1)になるのは、e=2 のときの 3, 487, 56598313 の3通りしか知られていないようです(A045616))
これらをうまく組み合わせると、全体で O(NlogN) で解くことができます。

埋め込みで解けてしまうのと、O(NN)との区別が難しいのとで、実際のコンテストに出すのは無理ですね。