10、欧拉函数
long long Calc_phi(long long a){
long long ret=a;
for(long long i=2;i*i<=a;i++)
if(!(a%i)){
ret=ret/i*(i-1);
while(!(a%i)) a/=i;
}
if(a>1) return ret/a*(a-1);
return ret;
}
11、欧拉筛法—欧拉函数
void Get_Phi(int n){
for(int i=2;i<=n;i++){
if(!Isitprim[i]) prim[++cnt]=i,phi[i]=i-1;
for(int j=1;j<=cnt && i*prim[j]<=n;j++){
Isitprim[i*prim[j]]=1;
if(i%prim[j]) phi[i*prim[j]]=phi[i]*(prim[j]-
1);
else phi[i*prim[j]]=phi[i]*prim[j];
}
}
}
12、中国剩余定理(CRT)
void CRT(){
for(int i=1;i<=N;i++) cin >> p[i] >> a[i],m*=p[i];
for(int i=1;i<=N;i++) ni[i]=calc_inv(m/p[i],p[i]);
for(int i=1;i<=N;i++) ans+=(a[i]*ni[i])*(m/p[i]),ans
%=m;
cout << ans << endl;
}
13、大步小步算法(BSGS)
void BSGS(long long a,long long b,long long p){
map<long,long> table;
map<long,long>::iterator it;
a%=p,b%=p;
table.clear();
if(!a){
if(!b) cout << 1 << endl;
else cout << "Orz, I cannot find x!" << endl;
return;
}
long long m=ceil(sqrt((double)p)),t=1,tmp=1,ans=-1,x,y;
for(int i=0;i<m;i++,t=t*a%p) table[t]=i;
for(int i=0;i<=m;i++){
exgcd(tmp,p,x,y);
x=((x*b)%p+p)%p;
it=table.find(x);
if(it!=table.end()){