ABC174 C - Repsept

備忘録

問題

atcoder.jp

回答

import sys, os, math, bisect, itertools, collections, heapq, queue, copy, array

# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from decimal import Decimal
# from collections import defaultdict, deque

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
INF = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    K = ii()

    ret = []
    for i in range(K + 1):
        if i == 0:
            ret.append(7 % K)
        else:
            ret.append((ret[i - 1] * 10 + 7) % K)
    for i in range(K + 1):
        if ret[i] == 0:
            print(i + 1)
            exit()
    else:
        print(-1)


if __name__ == '__main__':
    main()

考え方

数学的素養がないため、オイラーの定理が出てくるコンテスト全体の公式解説より、
kyopro_friends氏の公式解説が直感的にわかりやすかった。
ただし、感覚的な理解であるため、似た問題が出てきたとき、回答できるか不安ではある。。。

---

7, 77, 777, 7777, .... , 777777777, ...といった数列が存在するとき、
数列の1つ目の要素が7、
数列の2つ目の要素が7 * 10 + 7 = 77、
数列の3つ目の要素が77 * 10 + 7 = 777、
数列の4つ目の要素が777 * 10 + 7 = 7777と求めることが出来る。
つまり、数列aのi番目の要素は、a[i-1] * 10 + 7で求めることが出来る。

また、本問題は上記の数列の要素のうち、Kの倍数が登場するのは何項目であるか、
つまり、a[i] % K = 0となる要素を探索する。

複数の要素の中からある数字で割った余りが0になる要素を探す問題は、
よくある10 ** 9 + 7で割った余りを求める問題と同じで、
計算の途中で割った余りを使用して次の計算を行っても回答に影響がないことを利用して答えを探索する。

    K = 101
    a = [7, 77, 777, 7777, 77777]
    # 数列aの各要素をKで割った余り
    print(a[0] % K)  # 7
    print(a[1] % K)  # 77
    print(a[2] % K)  # 70
    print(a[3] % K)  # 0
    
    # 1つ目の要素(7)からKで割った余りを次の計算に使用しても
    # 結果は変わらない
    print(a[0] % K)                                                     # 7
    print(((a[0] % K) * 10 + 7) % K)                                    # 77
    print(((((a[0] % K) * 10 + 7) % K) * 10 + 7) % K)                   # 70
    print(((((((a[0] % K) * 10 + 7) % K) * 10 + 7) % K) * 10 + 7) % K)  # 0

上記のように、一つ前の要素から次の要素のKで割った余りを求めて、
求めた結果を次の計算に使用する。
計算をK回繰り返し、割った余りが0(Kの倍数となる要素)の位置を回答とする。