AtCoder Beginner Contest 174 C – Repsept をPython3で解く

Share

AtCoder上にある問題のうち、AtCoder Problemsでdiff 800以上と判定されているものを順番に解いていく企画。
基本的な考え方は全てコード中のコメントに入れてあるので、参照のこと。

出典:
AtCoder Beginner Contest 174 C – Repsept

septとはフランス語で7のこと。洒落た問題名かも。
ラテン語のseptemから来ていて、September(7番目の月)などに名残がある。なぜ7番目の月が9月なのかというと、かつては現在の3月が年初だったからで、2月だけ月が短いのは、年末に一年の日数を調整していた名残だったり。ま、それはさておき。

MODを使った考え方が要求される問題。加減乗除の除以外、加減乗についてはそのまま計算できるので、利用していこう。

# AtCoder Beginner Contest 174 C - Repsept
# https://atcoder.jp/contests/abc174/tasks/abc174_c
# tag: 整数 倍数 MOD 高橋君

# そのまま計算すると数列の数字がとんでもなく大きくなるので、
# MOD K を取って計算することを考える。
# 毎回の操作を
# (0 から始めて) 10 倍して 7 を足し、MOD K を取る
# だと考えることができる。

# また、毎回同じ操作を行っているということと、MOD K の
# 値が 0 ~ K-1 に限定されるということから、得られる値は
# 必ず循環するようになる。
# その循環の長さの上限は、MOD K の値が K 個に限定される
# ことから、K になる。
# よって K 回試行して割り切れなければ、0 を含まずに
# 循環が起こっていることになり、割り切れることはない。

def main():
    K = int(input())
    tmp = 0

    # K 回試行
    for i in range(K):
        # 10 倍して 7 を足し、MOD K を取り続ける
        tmp = (tmp * 10 + 7) % K

        # 0 になれば、割り切れたということなので、
        # 答えを返して終了
        if tmp == 0:
            print(i + 1)
            return

    # K 回やってダメなら割り切れることはない
    print(-1)

main()

Share

コメントを残す

メールアドレスが公開されることはありません。