题意：
你有一个随机数生成器，最初给定一个 \(0\leq
x\leq n-1\) 的整数作为随机种子.
这个随机数生成器会每次输出 \(x\)
并将 \(x^k \bmod n\) 作为新的 \(x\)。
你很快发现这个随机数生成器很渣。为了证明它很渣，你想要求出有多少个随机种子，使得这个随机数生成器会输出初始种子无穷多次。
数据范围：\(n,k\leq 10^{18}\)。
| Sample.in
n,k
Sample.out
ans
------
Sample.in
10 2
Sample.out
4
|
首先，我们注意这样一个事。
当 \(n\in \text{prime}\)
怎么做？
方程怎么写？
\[
x^{k^t}\equiv x\pmod{n}
\]
那么由于无论何时 \((x,n)=1\)，阶始终存在，所以有：
\[
k^t\equiv 1\pmod{ord_n(x)}
\]
也就是说：
\[
\gcd(k,ord_n(x))=1
\]
当我们知道阶为多少时，我们显然可以求出这个集合的大小。
我们现在枚举阶：
\[
\begin{aligned}
\sum_{d\mid\phi(n)} \phi(d)[\gcd(d,k)=1]\\
\sum_{d\mid \phi(n),\gcd(d,k)=1}\phi(d)
\end{aligned}
\]
显然我们令 \(T\) 为 \(\phi(n)\) 剔除所有 \(k\) 因子的结果。
\(T\) 的求法可以用以下代码体现：
| while(gcd(phi,k)!=1){
phi/=gcd(phi,k);
}
|
那么此时狮子可化简为：
\[
\begin{aligned}
\sum_{d\mid T} \phi(d)=T
\end{aligned}
\]
这是好的，那么我们有没有办法使得 \(n\not
\in \text{prime}\) 使用类似方法做呢？
考虑如果对于 \(n\not \in
\text{prime}\) 如果我们钦定 \(\gcd(x,n)=1\)，上述做法依然成立。
现在问题被这个 \(\gcd\)
卡住了，那就考虑 \(\gcd\)
会产生什么厉害东西。
\(g=\gcd(x,n)\)，我们考虑这样一个事，如果存在
\(p\)，使得 \(p^a\mid\mid x,p^b\mid\mid n,a<b\)。
那么这样 \(x^d\)，\(d\) 足够大时，\(p^b\mid x^d\)，这样 \(x^d\) 不可能和 \(x\) 同余。
所以 \(g,x,n\) 存在关系。
\(\gcd(g,\frac{n}{g})=1,\gcd(g,\frac{x}{g})=1\)。
那么设 \(x=g\cdot X,n=g\cdot N\)
\[
\begin{aligned}
x^{k^t}\equiv x\pmod{n}\\
(gX)^{k^t}\equiv gX\pmod{gN}\\
g^{k^t}X^{k^t}\equiv gX\pmod{gN}\\
\end{aligned}
\]
等式两边同除 \(g\)。
$$
\[\begin{aligned}
g^{k^t-1}X^{k^t}\equiv X\pmod{N}\\
g^{k^t-1}X^{k^t-1}\equiv 1\pmod{N}\\
k^t-1\equiv 0\pmod{ord_{N}(gX)}\\
k^t\equiv 1\pmod{ord_{N}(gX)}
\end{aligned}\]
$$
很眼熟是吧。
由于这个 \(gX\)
似乎并不那么平凡，我们只能先猜测这个的答案就是上面的答案。
也就是猜测 \(gX\) 与满足 \(k^t\equiv1\pmod{ord_{N}(x)}\) 的 \(x\in[1,N)\) 一一对应。
显然 \(ord_{N}(gX)=ord_N(gX\bmod
N),\gcd(gX,N)=1\)，所以每一个 \(gX\) 能仅对应一个满足的 \(x\)。
接下来考虑 \(gX\) 在 \(\bmod N\) 意义下互不相等。
反证法：如果 \(gA\equiv gB\pmod{N},gA\not
\equiv gB\pmod{n}\)，直接产生矛盾。（有关 \(A\equiv B\pmod{N}\) 的矛盾）
接下来考虑是否每一个满足的 \(x\)
都有一个 \(gX\) 与之对应。
因为 \(\gcd(g,N)=1\)
显然存在逆元。
\(gX\equiv
x\pmod{N},X=g^{-1}x\pmod{N}\)
显然能够对应。
所以当 \(g\) 确定时，\(k^t\equiv 1\pmod{ord_{N}(gX)}\) 满足的
\(gX\) 个数就是上面所说的 \(x\) 的个数。
所以我们可以枚举 \(g\)，从而算出结果。
复杂度 \(\mathcal{O(pollard-rho(n)+2^{\omega(n)}\log^2(n))}\)
后面可能是单 \(\log\)
但问题不大，复杂度瓶颈在于 \(pollard-rho(n)\)，即分解质因数复杂度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
|
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll mul(ll a,ll b,ll mod){
if(a>=mod) a%=mod;
if(b>=mod) b%=mod;
ll tmp=a*b-ll((long double)a/mod*b+0.5)*mod;
return tmp<0?tmp+mod:tmp;
}
ll p[]={3,5,7,11,13,17,19,23,29,31};
inline ll qpow(ll a,ll b,ll mod){
ll k=1;
while(b){
if(b&1) k=mul(k,a,mod);
a=mul(a,a,mod);b>>=1;
}return k;
}
inline bool chk(ll mod,ll p){
ll res=qpow(p,mod-1,mod);
ll b=mod-1;
if(res!=1) return 0;
while(b%2==0){
b/=2;
ll r=qpow(p,b,mod);
if(r==mod-1) return 1;
if(r!=1) return 0;
}
return 1;
}
inline bool prime(ll x){
if(x==2) return 1;
for(int i=0;i<9;i++){
if(x==p[i]) return 1;
if(x%p[i]==0) return 0;
if(chk(x,p[i])==0) return 0;
}return 1;
}
inline ll nxt(ll a,ll c,ll mod){
ll tmp=mul(a,a,mod)+c;
return tmp>=mod?tmp-mod:tmp;
}
inline ll gcd(ll a,ll b){
if(!b) return a;
return gcd(b,a%b);
}
inline ll pollard(ll n){
if(n==4) return 2;
ll a1=1ll*rand()*rand()%n,c=1ll*rand()*rand()%n;
ll a2=a1;
a1=nxt(a1,c,n),a2=nxt(nxt(a2,c,n),c,n);
int lim=1;
while(a1!=a2){
ll v=1;
for(int i=1;i<=lim&&a1!=a2;i++,a1=nxt(a1,c,n),a2=nxt(nxt(a2,c,n),c,n)){
ll backv=v;
v=mul(v,abs(a1-a2),n);
if(!v) return gcd(abs(a1-a2),n);
}
ll g=gcd(v,n);
if(g>1) return g;
if(lim<128) lim<<=1;
}
return pollard(n);
}
vector<ll> f;
inline void factor(ll n){
if(prime(n)){
f.push_back(n);
return ;
}
ll fac=pollard(n);
if(prime(fac)){
f.push_back(fac);
return factor(n/fac);
}
factor(fac);
factor(n/fac);
}
ll n,k;
inline ll getv(ll v,ll ph){
while(gcd(ph,k)!=1){
ph/=gcd(ph,k);
}
return ph;
}
vector<ll> a,b;
int lim;
ll ans;
inline void dfs(int n,ll res,ll ph){
if(n==a.size()){
if(res>1) ans+=getv(res,ph);
return ;
}
dfs(n+1,res,ph);
dfs(n+1,res*a[n],ph*b[n]);
}
signed main(){
cin>>n>>k;
f.clear();
factor(n);
ll N=n;
for(int i=1;i<f.size();i++){
if(f[i]!=f[i-1]){
ll res=1;
while(N%f[i-1]==0) N/=f[i-1],res=res*f[i-1];
a.push_back(res);
b.push_back(res/f[i-1]*(f[i-1]-1));
}
}
a.push_back(N);
b.push_back(N/(f.back())*(f.back()-1));
lim=a.size();
dfs(0,1ll,1ll);
cout<<ans+1;
}
|