[BZOJ4802]欧拉函数

bzoj

description

给出(n)，求(varphi(n))。(nle10^{18})

sol

(Pollard Rho)，存个代码。

code

#include<cstdio>
#include<algorithm>
#include<ctime>
using namespace std;
#define ll long long
ll p[100],len;
ll mul(ll x,ll y,ll mod){
	x%=mod;y%=mod;ll res=0;
	while(y){if(y&1)res=(res+x)%mod;x=(x+x)%mod;y>>=1;}
	return res;
}
ll fastpow(ll x,ll y,ll mod){
	x%=mod;ll res=1;
	while(y){if(y&1)res=mul(res,x,mod);x=mul(x,x,mod);y>>=1;}
	return res;
}
bool MR(ll n){
	if (n==2) return true;
	for (int i=1;i<=10;++i){
		ll x=1ll*rand()*rand()%(n-2)+2,p=n-1;
		if (fastpow(x,p,n)!=1) return false;
		while (~p&1){
			p>>=1;ll y=fastpow(x,p,n);
			if (mul(y,y,n)==1&&y!=1&&y!=n-1) return false;
		}
	}
	return true;
}
ll PR(ll n,ll c){
	ll i=0,k=2,x,y;x=y=1ll*rand()*rand()%(n-1)+1;
	while (1){
		x=(mul(x,x,n)+c)%n;
		ll d=__gcd((y-x+n)%n,n);
		if (d!=1&&d!=n) return d;
		if (x==y) return n;
		if (++i==k) y=x,k<<=1;
	}
}
void fact(ll n,ll c){
	if (n==1) return;
	if (MR(n)) {p[++len]=n;return;}
	ll p=n,k=c;
	while (p>=n) p=PR(p,c--);
	fact(p,k);fact(n/p,k);
}
int main(){
	ll n;scanf("%lld",&n);fact(n,666);
	sort(p+1,p+len+1);len=unique(p+1,p+len+1)-p-1;
	ll res=n;
	for (int i=1;i<=len;++i) res=res/p[i]*(p[i]-1);
	printf("%lld
",res);
	return 0;
}