Edit

【pythonでABC161を解説】F - Division or Subtraction

問題概要

問題ページ

F - Division or Subtraction
F - Division or Subtraction

問題ページへ移動する

問題文

正整数 \(N\) が与えられます。

\(2\) 以上 \(N\) 以下の整数 \(K\) を決めて、\(N\) が \(K\) 未満になるまで次の操作を繰り返し行います。

  • 操作：\(N\) が \(K\) で割り切れるとき、\(N\) を \(N/K\) に置き換える。そうでないとき、\(N\) を \(N-K\) に置き換える。

最終的に \(N\) が \(1\) になるような \(K\) の決め方は何通りありますか？

制約

  • \(2 \leq N \leq 10^{12}\)
  • \(N\) は整数

問題の考察

ACコード

import sys
import collections


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n = int(input().rstrip('\n'))
    d = collections.defaultdict(int)
    d[n]
    for i in range(1, int((n - 1) ** 0.5) + 1):
        if (n - 1) % i == 0:
            for j in [i, (n - 1) // i]:
                if j != 1:
                    d[j]
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            for j in [i, n // i]:
                if j not in d:
                    t_n = n
                    while t_n > 1:
                        if t_n % j == 0:
                            t_n //= j
                        else:
                            t_n %= j
                            break
                    if t_n == 1:
                        d[j]
    print(len(d))


if __name__ == '__main__':
    solve()

-Edit
-