bzoj

description

给出\(n\)，求\(\varphi(n)\)。\(n\le10^{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\n",res);

	return 0;

}