tookunn’s diary

主に競技プログラミング関係

AtCoder Beginner Contest 174 C - Repsept

問題

atcoder.jp

考察

7, 77, 777, ...の約数を列挙して、Kの約数を列挙して何か規則性があるのかとか探していたが
分からず。

数列をAとし、i番目の要素をA[i]とする。
Kの倍数ということは
A[i] mod K = 0ということ。

A[i + 1] = A[i] * 10 + 7なので、A[i]はmod Kをした値のまま扱えそう。

mod Kをした値だと値の種類は高々K個になる。
なので、AのK番目以降の要素は必ず既に出現した値になる。

既に出現した値以降は同じ順番で値が繰り返される。
なぜならA[i + 1] = A[i] * 10 + 7だから。

長さKの数列A(各要素にmod K適用されている)を作って
A[i] mod K = 0になるまでAをなめていく。