AtCoder Beginner Contest 174 C – Repsept を解いた記録
はじめに
私は解法を未証明のままコードを投げました．
悔い改めて問題の概要
\(7, 77, 777, \dots\)という数列の中で初めて\(K\)の倍数が登場するのは何項目であるか答えよ．ただし，登場しない場合は-1を出力せよ．
制約
\(1 \leq K \leq 10^6\)
解法
サンプルの入力例とそれに対応する出力例を見れば分かる通り，初めて\(K\)の倍数が登場する項では7が100万桁近く並んでいる可能性があります．
よって素直に7から順番に条件を満たすか確認する方法では攻略できないでしょう．
とりあえず，\(i\)項目\( (i=1, 2, 3, \dots) \)が条件を満たすかを判定する方法を考えます．
\(i\)項目が\(K\)の倍数であることと，\(i\)項目の数\(a_i\)が次式を満たすことは同値です．
\[
a_i \bmod K = 0
\]
例えば，7777（4項目）は101の倍数であり，\(7777 \bmod 101 = 0\)を満たします．
\(a_i\)を\(K\)で割った余りが0になれば問題の条件を満たすので，\(a_1\)から順番に\(a_i\)を\(K\)で割った余りを求めることを考えます．
コンテスト中の私は，
- \(xy \bmod p = ((x \bmod p) \times y) \bmod p\)となること
- 各\(i (i = 1, 2, \dots)\)について\(7 \times 10^{i-1} \bmod p\)の計算結果を記録し，和を取れば\(a_i\)をKで割った余りが求まること
を用いて\(a_1\)から順番に\(a_i\)を\(K\)で割った余りを求めました．
そして，ループを適当な回数回してもに\(a_i\)を\(K\)で割った余りが0にならない場合は-1を出力するようにしました．
有限回ループを回せば条件を満たす\(a_i\)の有無を判定できるかは未証明のまま提出したので大丈夫か不安になりましたが，ACできました．
実装例
感想など
ろくに精進しないまま強行出場したらレートが溶けました．昨年の夏も一瞬だけ緑コーダーになったあと，レートを溶かして茶色に逆戻りした前科があります．今年はそうならないようにしたいですね．
とりあえずはレートが溶ける流れを次に出場するコンテストで断ち切らねば…