PR算法 大数质因数分解优化

const int MAXN = 1000005 ;
 
int64_t mulEx(int64_t a , int64_t b , int64_t Mod) {
   ///logn快速乘
    if(!a) return 0 ;
    int64_t ans(0) ;
    while(b)
    {
   
		if(b & 1) ans = (ans + a) % Mod;
		a <<= 1 ;
		a %= Mod ;
		b >>= 1 ;
    }
    return ans ;
}
 
int64_t powEx(int64_t base , int64_t n , int64_t Mod)
{
   ///快速幂
    int64_t ans(1) ;
    while(n)
    {
   
        if(n & 1) ans = mulEx(ans , base , Mod) ;
        base = mulEx(base , base , Mod) ;
        n >>= 1 ;
    }
    return ans ;
}
 
bool check(int64_t a , int64_t d , int64_t n)
{
   
    if(n == a) return true ;
    while(~d & 1) d >>= 1 ;
    int64_t t = powEx(a , d , n) ;
    while(d < n - 1 && t != 1 && t != n - 1)
    {
   
        t = mulEx(t , t , n) ;
        d <<= 1 ;
    }
    return (d & 1) || t == n - 1 ;
}
 
bool isP(int64_t n)
{
    ///判断大数是否是质数
    if(n == 2) return true ;
    if(n < 2 || 0 == (n & 1)) return false ;
    static int p[5] = {
   2 , 3 , 7 , 61 , 24251} ;
    for(int i = 0 ; i < 5 ; ++ i) if(!check(p[i] , n - 1 , n)) return false ;
    return true ;
}
 
int64_t gcd(int64_t a , int64_t b)
{
   
    if(a < 0) return gcd(-a , b) ;
    return b ? gcd(b , a - b * (a / b)) : a ;
}
 
int64_t Pollard_rho(int64_t n , int64_t c)
{
   ///大数分解质因数
    int64_t i = 1 , k = 2 , x = rand() % n , y = x ;
    while(true)
    {
   
        x = (mulEx(x , x , n) + c) % n ;
        int64_t d = gcd(y - x , n) ;
        if(d != 1 && d != n) return d ;
        if(y == x) return n ;
        if(++ i == k)
        {
   
            y = x ;
            k <<= 1 ;
        }
    }
}
 
int64_t Fac[MAXN] , factCnt ;
///Fac存的是质因子,大小不一定按照顺序,有重复
void factorization(int64_t n)
{
   
    if(isP(n))
    {
   
        Fac[factCnt++] = n ;
        return ;
    }
    int64_t p(n) ;
    while(p >= n) p = Pollard_rho(p , rand() % (n - 1) + 1) ;
    factorization(p) ;
    factorization(n / p) ;
}
 
map<int64_t , int64_t> factMap ;
///遍历map的first表示因子,second表示次数
 
void getFactor(int64_t x)
{
   ///不用判断是否是质数,但是比较费时间
 /**因此最好先判断一下是否是质数**/
	srand(time(0)) ;
	factCnt = 0 ;
	factMap.clear() ;
	factorization(x) ;
	for(int i = 0; i < factCnt; ++i) ++ factMap[Fac[i]] ;
}