\(N \leq 10^{12}\) なので， \(O(N^{1/2})\) は間に合う． よって，約数列挙は大丈夫．
操作の逆を考えて， \(1\) から \(N\) を作ることを考える． \(x\) に \(\times K, + K\) をするが， いつでも出来るとは限らない．
- \(+ K \) は \(x \not\equiv 0 mod \ K\) のときのみ可能． また， このとき\(x + K \not \equiv 0 mod \ K\) となる．
- \(\times K\) はいつでも出来る．この操作の後は， \(mod \ K\) で \(0\)になる． よって， \(\times K\) の操作以降は， \(\times K\) しか出来なくなる．
以上から，操作列は $$+K, +K, \cdots, +K, \times K, \times K, \cdots \times K$$ の形になる． したがって，ある自然数\(x,y\) があって \(N = (xK + 1)K^{y}\) となる \(K\) が条件を満たす必要十分条件．
\(1\) からこの操作列を適用したとき，得られる値の中に \(N\) がある \(K \in [2,N]\) を求めたい． \(K\) の指数 \(y = 0\) or \(y \neq 0\) で場合分けする．
Case : \(\times K\) の操作を行わない
\(N = 1 + tK\) を満たす整数 \(t\) が取れる必要がある． よって， \(K\) は \(N-1\) の約数であることが必要．
Case : \(\times K\) の操作を行う
\(N\) は \(K\) の倍数であるから， \(K\) は \(N\) の約数である必要がある．
この2つのケースに現れる \(K \geq 2\) は，重複しない． なぜなら， \(N-1\)と \(N\) は互いに素であるから．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
vll divs(ll n){
vll v;
for(ll i=1; i*i <= n; i++) if(n%i == 0){
v.push_back(i);
if(n/i != i) v.push_back(n/i);
}
return v;
}
int main() {
ll n;
cin >> n;
// rem: div(n), div(n-1) は 1しか重複しない
vll v = divs(n);
vll tmp = divs(n-1);
v.insert(v.end(), all(tmp));
ll ans = 0;
for(auto k: v) if(k >= 2){
ll co = n;
while(co % k == 0) co /= k;
if(co % k == 1) ans++;
}
cout << ans << endl;
return 0;
}
