101615: [AtCoder]ABC161 F - Division or Subtraction
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:1
Solved:0
Description
Score : $600$ points
Problem Statement
Given is a positive integer $N$.
We will choose an integer $K$ between $2$ and $N$ (inclusive), then we will repeat the operation below until $N$ becomes less than $K$.
- Operation: if $K$ divides $N$, replace $N$ with $N/K$; otherwise, replace $N$ with $N-K$.
In how many choices of $K$ will $N$ become $1$ in the end?
Constraints
- $2 \leq N \leq 10^{12}$
- $N$ is an integer.
Input
Input is given from Standard Input in the following format:
$N$
Output
Print the number of choices of $K$ in which $N$ becomes $1$ in the end.
Sample Input 1
6
Sample Output 1
3
There are three choices of $K$ in which $N$ becomes $1$ in the end: $2$, $5$, and $6$.
In each of these choices, $N$ will change as follows:
- When $K=2$: $6 \to 3 \to 1$
- When $K=5$: $6 \to 1$
- When $K=6$: $6 \to 1$
Sample Input 2
3141
Sample Output 2
13
Sample Input 3
314159265358
Sample Output 3
9