ABC161 F - Division or Substraction

問題原文

atcoder.jp

問題要旨

正整数 が与えられる。２以上 以下の整数 を決めて、 となるまで以下の操作を繰り返す。

• なら、 で置き換える。そうでないなら、 で置き換える。

最終的に が１になるような はいくつあるか？

• 

解法

本番は実験の結果通してしまった。解説PDFがすごいわかりやすい。
まず、 割り算をしない場合、 は変化しない。
つまり、最終的に １ になるためには、 であればよい。 そしてそのような は、１以外の の約数。（N / K = x あまり １などとして式変形すればわかる）

また、１回以上割り算が起こるような は、 の約数。
これらについては実際に操作を行って判定しても十分間に合う。

実装

最後に一応集合をとっているけど、 と は互いに素だからしなくていいらしい。
（ と が２以上の共通の約数 を持つと仮定すると、 と は の倍数ということになる。 の倍数と の倍数の差は の倍数だが、 になって、これは仮定に矛盾する。）

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)))

感想

ノリで通してしまったけど、すごい学びが多い問題だった。
時間を空けてちゃんと証明して解きなおしたいな。