Description 给出一整数n，求phi Input 一个正整数n(nM=1e18) Output 输出phi(n) Sample Input 8 Sample Output 4 Solution 用Pollard-rho对n素因子分解即可 Code
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<cmath> #include<vector> #include<queue> #include<map> #include<set> #include<ctime> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int,int>P; const int INF=0x3f3f3f3f,maxn=200001; map<ll,int>factor; map<ll,int>::iterator it; vector<int>prime; int is_prime[maxn]; void get_prime() { is_prime[0]=is_prime[1]=0; for(int i=2;i<maxn;i++)is_prime[i]=1; for(int i=2;i<maxn;i++) if(is_prime[i]) { prime.push_back(i); for(int j=2*i;j<maxn;j+=i)is_prime[j]=0; } } ll gcd(ll a,ll b) { if(a==0)return 1; if(b==0)return a; return gcd(b,a%b); } ll Mul(ll a,ll b,ll p) { return (a*b-(ll)(a/(ld)p*b+1e-3)*p+p)%p; } ll Pow(ll a,ll b,ll c) { a%=c; ll ans=1; while(b) { if(b&1)ans=Mul(ans,a,c); a=Mul(a,a,c); b>>=1; } return ans; } bool Miller_Rabin(ll n,int times) { if(n<2)return 0; if(n==2)return 1; if(!(n&1))return 0; ll q=n-1; int k=0; while(q%2==0)k++,q>>=1; for(int i=0;i<times;i++) { ll a=rand()%(n-1)+1; ll x=Pow(a,q,n); if(x==1)continue; bool found=0; for(int j=0;j<k;j++) { if(x==n-1) { found=1; break; } x=Mul(x,x,n); } if(found)continue; return 0; } return 1; } ll Pollard_rho(ll n,int c) { ll x=2,y=2,d=1; while(d==1) { x=Mul(x,x,n)+c; y=Mul(y,y,n)+c; y=Mul(y,y,n)+c; d=gcd(abs(x-y),n); } if(d==n)return Pollard_rho(n,c+1); return d; } bool Is_Prime(ll n) { if(n<maxn)return is_prime[n]; return Miller_Rabin(n,20); } void Find_Factor(ll n) { if(Is_Prime(n)) { factor[n]++; return ; } else { for(int i=0;i<prime.size();i++) while(n%prime[i]==0) factor[prime[i]]++,n/=prime[i]; if(n!=1) { if(Is_Prime(n))factor[n]++; else { ll d=Pollard_rho(n,1); Find_Factor(d),Find_Factor(n/d); } } } } int main() { ll n; scanf("%lld",&n); get_prime(); factor.clear(); Find_Factor(n); ll ans=n; for(it=factor.begin();it!=factor.end();it++) ans=ans/(it->first)*(it->first-1); printf("%lld\n",ans); return 0; }