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()
関連
