?

/** CODE VS 4939 歐拉函數 質因數啟發式分解 鏈接:http://codevs.cn/problem/4939/ */#include<bits/stdc++.h> #define ll long long using namespace std;/**********************************************Head-----Template****************************************/ bool Finish_read; template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;} template<class T>inline void print(T x){if(x/10!=0)print(x/10);putchar(x%10+'0');} template<class T>inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('\n');} template<class T>inline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);} inline ll gcd(ll a,ll b){ return b==0?a:gcd(b,a%b);} inline ll lcm(ll a,ll b){ll gg=gcd(a,b);a/=gg;if(a<=LLONG_MAX/b) return a*b;return LLONG_MAX;} /********************************Head----Temlate**********************************************/inline ll mul(ll a, ll b, ll mod){return a%=mod, b%=mod, (a*b-(long long)((long double)a*b/mod+1e-3)*mod+mod)%mod; }inline ll ksm(ll x, ll y, ll mod){ll ans=1;for (;y;y>>=1, x=mul(x, x, mod)) if (y&1) ans=mul(ans, x, mod);return ans; }/********** Miller_Rabin 素數判定 利用費馬小定理,以prime為基，不以隨機函數進行測試; 利用a^(p-1)=1(mod p) 利用較大概率默認p為素數,也就是忽略了偽素數的情況 優化：提取p-1中2的倍數,p-1=2^(k)*t,先算出a^t mod p 再進行不斷平方，暴力次數[0,k]，直到中間過程存在ans = p-1 則所判數字為素數 */ bool Miller_Rabin(ll n){static const ll prime[]={2, 3, 5, 7, 11, 13, 17, 19, 23};if (n<=23){ for (int i=0;i<9;i++) if (n==prime[i]) return true;return false;}if (~n&1) return false;for (int t=0;t<9;t++){ll y=n-1; int bit=0;for (;~y&1;y>>=1,bit++);ll x=ksm(prime[t],y,n);if (x==1) goto ed;//goto 減少標記次數for (;bit--;x=mul(x, x, n)) if (x==n-1) goto ed;//判處最后的ansreturn false;ed:;}return true; }vector<ll>vec;//存儲質因數分解結果(無序) /************* Pollard_Rho質因數分解:啟發式分解時間復雜度:O(n^(1/4)),空間復雜度:lg(n)首先確定一個數x為n的質因數,隨機找的話概率為1/p; 如果通過某種倍增的規律進行遞推x=(x*x+c)%n，可以得到兩個數x1,x2 利用gcd(abs(x1-x2),n)>1,使得x1 - x2 不斷向左式進行靠近 由此分解出來的差值為n的質因數的概率顯著增加最后返回兩種結果: op 1:因數 op 2 :x1 == x2 也就是說當前的倍增數c不滿足當前解,那么就需要換個c進行嘗試;換c進行嘗試的過程，必然很隨機，因得到的ans是存在重復且無序的*/ void Pollard_Rho(ll n){if (Miller_Rabin(n)) return void (vec.push_back(n));for (ll c=1;;c++){for (ll i=1,x2=0,x1=c;;x1=mul(x1,x1,n)+c,i++){if (x1==x2) break;ll d=gcd(n, x1>=x2?x1-x2:x2-x1);if (1<d&&d<n) return Pollard_Rho(d),Pollard_Rho(n/d),void();if (i==(i&-i)) x2=x1;}} } int main(){for (;;){ll n;read(n); if(n==0) break;Pollard_Rho(n);sort(vec.begin(),vec.end()); int num = unique(vec.begin(),vec.end())-vec.begin();ll ans=n;for(int i=0;i<num;i++) ans=ans/vec[i]*(vec[i]-1);printf("%lld\n",ans);vec.clear();}return 0; }

?

總結

以上是生活随笔為你收集整理的CODE VS 4939 欧拉函数 质因数启发式分解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。