Division or Subtraction

题目描述

给定一个正整数 $N$。 我们将选择一个整数 $K$，其在 $2$ 到 $N$（包含）之间，然后重复下面的操作直到 $N$ 小于 $K$。

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

有多少种 $K$ 的选择会使得最终 $N$ 变为 $1$？

输入格式

输入按照以下格式从标准输入给出： $N$

输出格式

输出使得 $N$ 最终变为 $1$ 的 $K$ 的选择数。

6

3

3141

13

314159265358

9

提示

$2 \leq N \leq 10^{12}$ $N$ 是一个整数。有三种 $K$ 的选择会使得 $N$ 最终变为 $1$：$2$、$5$ 和 $6$。 在每一种选择中，$N$ 的变化如下：

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

标签: AtCoder|abc161F

来源

AtCoder|abc161F