C - Repsept

[hxrxchang]

https://atcoder.jp/contests/abc174/tasks/abc174_c

問題

7, 77, 777, 7777, ... と続く無限の数列の中に、Kの倍数となる要素は何番目か。 ない場合は -1 を出力せよ。

方針

前提知識として、モジュラー算術の性質 を知っておく必要がある。 これは、足し算、引き算、掛け算に関して、その答えのmodを求めるとき、あらかじめ各項のmod を求めて計算して、それのmod をとっても答えは等しいという性質がある。 例えば足し算の場合、(a + b) % mod = ((a % mod) + (b % mod)) % mod となる。

https://chat.openai.com/c/d32a33f7-0529-4c95-af26-013d49e20212

Nは最大 10**6 なので、最大10**6桁の数字に対してmodを求めることになりこれは計算量が膨大である。 [7, 77, 777, 7777....]の数列の要素 i が、次の項に遷移するためには i * 10 + 7 すればいいが、この計算にモジュラー算術の性質を使って、i * 10 % K + 7 % Kで更新させていけば大きな数字になることを防げる。

次に、どこまで調べたら打ち切れるかを考える。 上の説明の通り、Kで割って余りを求める対象は、既にKで割った余りであることがわかる。そのため、余りを求める対象の種類は最大1~KのK種類しかない。そのため、繰り返し同じ余りが出てくるということは無限に巡回することになり、Kの倍数は存在しないことがわかるのでそこで打ち切ってよい。

K = int(input())

visited = [False] * (K + 1)
tmp = 7 % K
cnt = 1

while True:
    rem = tmp % K
    if rem == 0:
        print(cnt)
        break
    if visited[rem]:
        print(-1)
        break
    visited[rem] = True
    tmp = tmp * 10 % K + 7 % K
    cnt += 1

https://atcoder.jp/contests/abc174/submissions/52730672