大数分解Pollard_rho模板

发现我之前写的Pollard_rho模板是假的。。。
学(抄)了一发真的，但跑的贼慢

ll mult(ll x,ll y,ll Mo) {
    x%=Mo;y%=Mo;
    ll tmp=(ll)((long double)x*y/Mo+1e-8)*Mo;
    return (x*y-tmp+Mo)%Mo;
}

ll pwr(ll x,ll Mo) {
    ll z=1;x%=Mo;y%=(Mo-1);
    for(;y;y>>=1,x=mult(x,x,Mo))
        if (y&1) z=mult(z,Mo);
    return z;
}

ll gcd(ll x,ll y) {
    if (!x) return 1;
    if (x<0) return gcd(-x,y);
    return y?gcd(y,x%y):x;
}

bool check(ll a,ll n,ll x,ll t) {
    ll res=pwr(a,n),lst=res;
    fo(i,1,t) {
        res=mult(res,res,n);
        if (res==1&&lst!=1&&lst!=n-1) return 1;
        lst=res;
    }
    if (res!=1) return 1;
    else return 0;
} 

bool Miller_Rabin(ll n) {
    if (n<2) return 0;
    if (n==2) return 1;
    if (!(n&1)) return 0;
    ll x=n-1,t=0;
    while (!(x&1)) x>>=1,t++;
    fo(i,S) {
        ll a=rand()%(n-1)+1;
        if (check(a,n,t)) return 0;
    }
    return 1;
}

ll Pollard_rho(ll n,ll t) {
    int i=1,k=2;
    ll x0=rand()%n,y=x0;
    while (1) {
        i++;
        x0=(mult(x0,x0,n)+t)%n;
        ll d=gcd(y-x0,n);
        if(d!=1&&d!=n) return d;  
        if(y==x0) return n;  
        if(i==k) y=x0,k<<=1;  
    }  
}

void find(ll n) {
    if (n==1) return;
    if (Miller_Rabin(n)) {
        pri[++tot]=n;
        return;
    }
    ll p=n;
    while (p>=n) p=Pollard_rho(p,rand()%(n-1)+1);
    find(p);find(n/p);
}