整数問題って感じの問題でした。
正整数 $N$ が与えられます。
$2$ 以上 $N$ 以下の整数 $K$ を決めて、$N$ が $K$ 未満になるまで次の操作を繰り返し行います。操作：$N$ が $K$ で割り切れるとき、$N$ を $N/K$ に置き換える。そうでないとき、$N$ を $N−K$ に置き換える。
最終的に $N$ が $1$ になるような $K$ の決め方は何通りありますか？
https://atcoder.jp/contests/abc161/tasks/abc161_f
愚直に操作を書いてすべての K で判定しようとすると、 N が大きすぎるために死んでしまいます。そこで条件を使ってイイ感じに絞り込みができないかを考えてみます。
絞り込み → しらみつぶし が整数問題の基本ですよね
条件を満たす $K$ をもう少し絞り込みたい
操作をもとに $K$ を用いて $N$ をイイ感じに表現してみたいと思います。等式もしくは不等式が作れれば条件も出せますしね。
操作自体は次の2つにまとめられます。
- K で割れるだけ割る
- K を引けるだけ引く
$K$ で割れるだけ割る操作は、 $N = K^a M$ のように表現してやれば、 $N \to M$ となる操作と考えることができます。（ $a \geq 0$ ）
そして、これが済んだ状態 （ $M$ ） に対して、 $K$ を引けるだけ引くと、残った分は $M/K$ のあまり、 $M \% K$ となります。
これが $1$ になればよいので、 $M = bK + 1$ と表現できそうですね。
結局 $N$ は非負整数 $a, b$ と条件を満たす $K$ を用いて、次の形で表現できることがわかります。
$$ N = K^a (bK+1)$$
さて、等式が得られたのでこれを用いて絞り込みを行いましょう〜
約数・倍数関係に着目してみると、 $K$ は $N$ の約数もしくは $N-1$ の約数であることが必要であることがわかります。これでかなり絞れそうなので、あとはしらみつぶし（全探索）でなんとかしましょう。
整数 $n$ の約数の全列挙は次のように、 $\sqrt{n}$ まで見れば相方も列挙できることに注意して工夫して計算するとよさそうです。
# 約数を全列挙する関数
def make_divisors(n):
divisors = []
for i in range(1, int(n ** 0.5) + 1):
if n % i == 0:
divisors.append(i)
if i != n // i:
divisors.append(n // i)
divisors.sort()
return divisors以上、回答例はこんな感じです。
def make_divisors(n):
divisors = []
for i in range(1, int(n ** 0.5) + 1):
if n % i == 0:
divisors.append(i)
if i != n // i:
divisors.append(n // i)
divisors.sort()
return divisors
N0 = int(input())
ans = 0
# N = K^a (bK + 1) と表現できるので K は N or N-1 の約数であることが必要
K_cand = set(make_divisors(N0) + make_divisors(N0 - 1))
for K in K_cand:
N = N0
if K == 1: # K = 1 を除外
continue
else:
while N % K == 0:
N = N // K # 割れるだけ割る
N = N % K # 引けるだけ引く
if N == 1:
ans += 1
print(ans)