传送门
Pollard−rhoPollard-rhoPollard−rho模板题。
题意简述：求ϕ(n),n≤1e18\phi(n),n\le 1e18ϕ(n),n≤1e18
先把nnn用Pollard−rhoPollard-rhoPollard−rho分解质因数，然后就可以算了。
代码：
#include<bits/stdc++.h>
#include<tr1/unordered_map>
#define ri register int
using namespace std;
typedef unsigned int uint;
typedef long long ll;
tr1::unordered_map<ll,int>S;
int pri[10]={2,3,5,7,11,13,17,19,23,29};
vector<ll>fac;
inline uint unit(){
static uint state0=19491001;
state0^=(state0>>13);
state0^=(state0<<17);
state0^=(state0>>5);
return state0;
}
inline ll ksc(ll a,ll b,ll mod){return (a*b-(ll)((long double)a/mod*b)*mod+mod)%mod;}
inline ll ksm(ll a,ll p,ll mod){ll ret=1;a%=mod;for(;p;p>>=1,a=ksc(a,a,mod))if(p&1)ret=ksc(ret,a,mod);return ret;}
inline bool check(ll x,ll a,ll s,ll t){
a=ksm(a,t,x);
ll p=a;
if(a==1||a==x-1)return 1;
while(s--){
a=ksc(p,p,x);
if(a==1&&(p!=x-1&&p!=1))return 0;
p=a;
}
return p==1;
}
inline bool MRT(ll x){
if(x==2||x==3)return fac.push_back(x),1;
if(!(x&1))return 0;
if(x%6!=1&&x%6!=5)return 0;
ll s=0,t=x-1;
while(!(t&1))t>>=1,++s;
for(ri i=0;i<10;++i){
if(x==pri[i])return fac.push_back(x),1;
if(!(x%pri[i]))return 0;
if(!check(x,pri[i],s,t))return 0;
}
return fac.push_back(x),1;
}
inline ll F(ll x,ll c,ll mod){return (ksc(x,x,mod)+c)%mod;}
inline ll gcd(ll a,ll b){while(b){ll t=a;a=b,b=t%a;}return a;}
inline ll rho(ll n,ll c){
ll x=unit()%n+1,y=x,p=1;
for(ri i=1,k=2;p==1;++i){
x=F(x,c,n),p=gcd(y>x?y-x:x-y,n);
if(i==k)y=x,k<<=1;
}
return p;
}
inline void solve(ll n){
if(n==1||MRT(n))return;
ll d=rho(n,unit()%n);
while(d==n)d=rho(n,unit()%n);
solve(n/d),solve(d);
}
int main(){
freopen("lx.in","r",stdin);
ll n,ans;
scanf("%lld",&n),solve(n),ans=n;
for(ri i=fac.size()-1;~i;--i){
if(S[fac[i]])continue;
S[fac[i]]=1,ans=ans/fac[i]*(fac[i]-1);
}
return cout<<ans,0;
}