Pollard-Rho 還是很容易理解的，其作用就是找一個數(shù) \(n\) 的一個非平凡約數(shù)。(非平凡約數(shù)即不是 \(1\) 也不是它本身的約數(shù))。
復(fù)雜度大致是 \(n^{\frac{1}{4}} \log n\)。

首先引入生日悖論：一年 \(365\) 天，當(dāng)一個房間中的人數(shù)至少為 \(23\) 人時，兩個人的生日日期相同的概率大于等于 \(50 \%\)。
這個就讓我們明白了在值域?yàn)?\(N\) 時，隨機(jī) \(O(\sqrt N)\) 次就會出現(xiàn)一對相同的數(shù)。

于是我們設(shè)計(jì)一個偽隨機(jī)數(shù) \(f(x) = x^2 + c \pmod n\)，\(c\) 為隨機(jī)的一個數(shù)。

為什么要這樣做呢？我們設(shè) \(n\) 最小的非平凡約數(shù)時 \(p\)，首先能發(fā)現(xiàn)一個很好的性質(zhì)，若我們得到這個序列： \(x_1,x_2=f(x_1),x_3=f(x_2),....\)，最終會形成一個循環(huán)節(jié)，也就像 \(\rho\) 一樣。而且還滿足：若 \(x \equiv y \pmod p\)，\(f(x) \equiv f(y) \pmod p\)。由上文的生日悖論，可以得到出現(xiàn) \(x_i \equiv x_j \pmod p\) 的期望復(fù)雜度是 \(O(\sqrt p)\) 的，但我們并不知道 \(p\) 為多少，我們只知道當(dāng) \(x_i \equiv x_j \pmod p\) 時，\(\gcd(|x_i - x_j|,n)\) 不為 \(1\)，而這也就是我們對重復(fù)了的情況的判斷標(biāo)準(zhǔn)。（記住是不為 \(1\)，所以找到的約數(shù)可能是 \(n\)。）

然后我們相當(dāng)于就是需要在較快的時間內(nèi)判斷環(huán)是否出現(xiàn)。

這里簡單介紹一下 floyd 判環(huán)，因?yàn)檫@是主要思想，其他做法也只是這個做法的優(yōu)化。我們把 \(x_i \equiv x_j \pmod p\) 當(dāng)成兩個人在環(huán)上跑，其中一個人超了另一個人一圈。所以我們使用兩個指針，一個每次跳一步，另一個每次跳兩步，然后每次做差判斷是出現(xiàn)環(huán)。

至于優(yōu)化，這里講倍增優(yōu)化，我們第 \(k\) 輪讓后面那個指針跳 \(2^k\) 步，前面指針不動，如果出現(xiàn) \(gcd\) 不為 \(1\) 的情況，就說明出現(xiàn)了環(huán)。

我們考慮到如果每次都要判 \(\gcd\) 就要帶一個 \(\log\)，也就是 \(O(\sqrt p \log n)\)，而我們知道若 \(\gcd(|x_i - x_j|,n)\) 不為 \(1\)，那 \(\gcd(\Pi|x_i - x_j| \bmod n,n)\) 也不為 \(1\)，所以我們考慮計(jì)算乘積與 \(n\) 的 \(\gcd\)，我們考慮每 \(k\) 次就算一次 \(\gcd\)，那復(fù)雜度就變成了 \(O(\frac{\sqrt p \log n}{k} + \sqrt p)\)，這里 \(k\) 是一個常數(shù)，自己定義即可。

分解質(zhì)因數(shù)還需要 Miller-Rabin 的輔助，Miller-Rabin 相對簡單，故不再贅述。

分解質(zhì)因數(shù)代碼：

#define ll __int128
#define int long long
struct Miller_Rabin{
    int pri[13]={0,2,3,5,7,11,13,17,19,23,29,31,37},cnt=12;  
    inline bool chk(ll n,ll p){
        if(n%p==0) return false;
        ll num=n-1,t=0;
        while(num%2==0) num/=2,t++;
        ll v=qpow(p,num,n),s=0;
        if(v==1) return true;
        for(;s<t;s++){
            if(v==n-1) return true;
            v=v*v%n;
        }
        if(s==t) return false;
        return true;
    }
    inline bool is_pri(int n){
        for(int i=1;i<=cnt;i++){
            if(pri[i]==n) return true;
            if(!chk(n,pri[i])) return false;
            
        }
        return true;
    }
}Test;
struct Pollard_Rho{
    int k=127;
    inline ll F(ll x,ll c,ll mod){
        x%=mod;
        return (x*x+c)%mod;
    }
    inline ll abs(ll x){return (x>0)?x:-x;}
    inline int gt_div(ll x){
        int c=rand()%(x-1)+1;
        ll s=0,t=0,v=1;
        ll tt=0;
        for(int w=1;;w<<=1,s=t){
            for(int num=1;num<=w;num++){
                tt++;
                t=F(t,c,x);
                v=v*(abs(t-s)%x)%x;
                if(!v) return x;
                if(num%k==0){
                    int d=__gcd(v,x);
                    if(d>1) return d;
                }
            }
            int d=__gcd(v,x);
            if(d>1) return d;
        }
    }
}Pr;
inline void fac(int x){
    if(x==1) return ;
    if(Test.is_pri(x)){
        cout<<x<<' ';
        return ;
    }
    int now=x; while(now==x) now=Pr.gt_div(x);
    x/=now;
    fac(x); fac(now);
}