配点 : $600$ 点

問題文

正整数 $N$ が与えられます。

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

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

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

制約

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

入力

入力は以下の形式で標準入力から与えられる。

$N$

出力

最終的に $N$ が $1$ になるような $K$ の決め方が何通りあるか出力せよ。

6

3

最終的に $N$ が $1$ になるような $K$ は $2,5,6$ の $3$ 通りです。

それぞれのとき、$N$ は次のように変化します。

• $K=2$ のとき：$6 \to 3 \to 1$
• $K=5$ のとき：$6 \to 1$
• $K=6$ のとき：$6 \to 1$

3141

13

314159265358

9