Multiply and pow Function:
//计算 (a*b)%c. a,b都是ll的数，直接相乘可能溢出的
// a,b,c <2^63
ll mult_modq(ll a,ll b,ll c){
a %= c;
b %= c;
ll ret = ;
while(b){
if(b & ){ret += a;ret %= c;}
a <<= ;
if(a >= c)a %= c;
b >>= ;
}
return ret;
} //计算 x^n %c
ll pow_mod(ll x,ll n,ll mod){
if(n == )return x%mod;
x %= mod;
ll tmp = x;
ll ret = ;
while(n){
if(n & ) ret = mult_mod(ret, tmp, mod);
tmp = mult_mod(tmp, tmp, mod);
n >>= ;
}
return ret;
}
Miller_Rabin Prime Number test：
return TRUE when Prime Number (BE POSSIBLITY)
return FALSE when not a Prime Number
//以a为基,n-1=x*2^t a^(n-1)=1(mod n) 验证n是不是合数
//一定是合数返回true,不一定返回false
bool check(ll a,ll n,ll x,ll t){
ll ret = pow_mod(a, x, n);
ll last = ret;
for(int i = ; i <= t; ++i){
ret = mult_mod(ret,ret,n);
if(ret == && last != && last != n - ) return true;//合数
last = ret;
}
if(ret != ) return true;
return false;
} // Miller_Rabin()算法素数判定
//是素数返回true.(可能是伪素数，但概率极小)
//合数返回false; bool Miller_Rabin(ll n){
if(n < ) return false;
if(n == ) return true;
if((n & ) == ) return false;//偶数
ll x = n - ;
ll t = ;
while((x & ) == ){x >>= ; ++t;}
for(int i = ; i <S ; ++i){
ll a = rand() % (n - ) + ;
if(check(a,n,x,t))
return false;//合数
}
return true;
}
Pollard_rho Algorithm
The quality factor decomposition :
ll factor[];//质因数分解结果（刚返回时是无序的）
int tol;//质因数的个数。数组小标从0开始 ll gcd(ll a,ll b){
if(a == ) return ;
if(a < ) return gcd(-a,b);
while(b){
ll t = a % b;
a = b;
b = t;
}
return a;
} ll Pollard_rho(ll x,ll c){
ll i = , k = ;
ll x0 = rand()%x;
ll y = x0;
while(){
++i;
x0 = (mult_mod(x0,x0,x)+c)%x;
ll d = gcd(y-x0,x);
if(d != && d != x) return d;
if(y == x0) return x;
if(i == k){y = x0; k += k;}
}
}
//对n进行素因子分解
void findfac(ll n){
if(Miller_Rabin(n)){
factor[tol++] = n;
return;
}
ll p = n;
while(p >= n) p = Pollard_rho(p,rand()%(n-)+);
findfac(p);
findfac(n/p);
}