AtCoder Beginner Contest 174 C - Repsept
問題
考察
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をなめていく。