AT_abc161_f [ABC161F] Division or Subtraction

题目描述

给定一个正整数 $N$。

你可以选择一个满足 $2 \leq K \leq N$ 的整数 $K$，并重复进行以下操作，直到 $N$ 小于 $K$ 为止：

• 操作：如果 $N$ 能被 $K$ 整除，则将 $N$ 替换为 $N/K$。否则，将 $N$ 替换为 $N-K$。

请问，有多少种选择 $K$ 的方式，能够使最终 $N$ 变为 $1$？

输入格式

输入为一行，包含一个整数 $N$。

输出格式

输出能够使最终 $N$ 变为 $1$ 的 $K$ 的种数。

输入输出样例 #1

输入 #1

6

输出 #1

3

输入输出样例 #2

输入 #2

3141

输出 #2

13

输入输出样例 #3

输入 #3

314159265358

输出 #3

9

说明/提示

限制条件

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

样例解释 1

能够使最终 $N$ 变为 $1$ 的 $K$ 有 $2, 5, 6$ 共 $3$ 种。对于每种 $K$，$N$ 的变化如下：

• 当 $K=2$ 时：$6 \to 3 \to 1$
• 当 $K=5$ 时：$6 \to 1$
• 当 $K=6$ 时：$6 \to 1$

由 ChatGPT 4.1 翻译