ABC161 F - Division or Substraction
問題原文
問題要旨
正整数 が与えられる。2以上
以下の整数
を決めて、
となるまで以下の操作を繰り返す。
なら、
で置き換える。そうでないなら、
で置き換える。
最終的に が1になるような
はいくつあるか?
解法
本番は実験の結果通してしまった。解説PDFがすごいわかりやすい。
まず、 割り算をしない場合、 は変化しない。
つまり、最終的に 1 になるためには、 であればよい。 そしてそのような
は、1以外の
の約数。(N / K = x あまり 1などとして式変形すればわかる)
また、1回以上割り算が起こるような は、
の約数。
これらについては実際に操作を行って判定しても十分間に合う。
実装
最後に一応集合をとっているけど、 と
は互いに素だからしなくていいらしい。
( と
が2以上の共通の約数
を持つと仮定すると、
と
は
の倍数ということになる。
の倍数と
の倍数の差は
の倍数だが、
になって、これは仮定に矛盾する。)
N = int(input()) ans = [] for n in range(1, int(N ** 0.5) + 1): if (N - 1) % n == 0: ans.append(n) ans.append((N - 1) // n) for k in range(2, int(N ** 0.5) + 1): if N % k != 0: continue x = N while x % k == 0: x //= k if x % k == 1: ans.append(k) print(len(set(ans)))
感想
ノリで通してしまったけど、すごい学びが多い問題だった。
時間を空けてちゃんと証明して解きなおしたいな。