bzoj 4802 欧拉函数 (pollardrho大数质因数分解)
发布时间:2020-12-14 03:23:38 所属栏目:大数据 来源:网络整理
导读:bzoj4802 求 (10^{18}) 级别的数的欧拉函数。 pollardrho算法分解大数质因数即可。(主要是存模板) #include bits/stdc++.h using namespace std; typedef long long ll;ll sed= 20170831 ,mo=LLONG_MAX,rt= 1 ;ll rand_() { rt=(((rt%sed) 16 )mo); retu
bzoj4802 求(10^{18})级别的数的欧拉函数。 pollardrho算法分解大数质因数即可。(主要是存模板) #include <bits/stdc++.h> using namespace std; typedef long long ll; ll sed=20170831,mo=LLONG_MAX,rt=1; ll rand_() { rt=(((rt%sed)<<16)&mo); return rt; } ll range(int l,int r) { return rand_()%(r-l+1)+l; } ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); } ll SlowMul(ll a,ll b,ll mo) { ll ret=0; while(b) { if(b&1) ret=(ret+a)%mo; a=(a+a)%mo; b>>=1; } return ret; } ll QuickPow(ll x,ll k,ll mo) { ll ret=1ll; while(k) { if(k&1) ret=SlowMul(ret,x,mo); x=SlowMul(x,mo); k>>=1; } return ret; } bool MillerRabin(ll x) { if(x==2) return true; int t=0; ll u=x-1; while(!(u&1)) { t++; u>>=1; } int s=20; ll now,pre; while(s--) { ll a=range(1,x-1); now=QuickPow(a,u,x); for(int z=0;z<t;z++) { pre=now; now=SlowMul(now,now,x); if(now==1 && pre!=1 && pre!=x-1) return false; } if(now!=1) return false; } return true; } ll PollardRho(ll n,int c) { ll x2=range(1,n-1),x1=x2,p,k=2; int tim=1; while(1) { tim++; x2=(SlowMul(x2,x2,n)+c)%n; p=gcd(n,(x1-x2+n)%n); if(p>1 && p<n) { return p; } if(x1==x2) return n; if(tim==k) { x1=x2; k<<=1; } } } vector<ll > prs; void proce(ll x,int c) { if(x==1) return; if(MillerRabin(x)) { prs.push_back(x); return; } int p=x,tmp=c; while(p>=x) p=PollardRho(p,c--); proce(p,tmp); proce(x/p,tmp); } ll x; int main() { scanf("%lld",&x); prs.clear(); proce(x,7); sort(prs.begin(),prs.end()); ll ans=x,pre=0; for(int i=0;i<(int)prs.size();i++) { if(prs[i]!=pre) ans=ans/prs[i]*(prs[i]-1),pre=prs[i]; } printf("%lldn",ans); return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |