hdu 4344 大数分解

就是个pallord_rho的裸题…

这里发现一个很神奇的东西，本来这个算法就是依赖随机化和人品的，我如果用120开始往下减作为随机化函数的随机化因子，只用4000多ms，如果直接rand就会t掉…真神奇啊，以后写pallord_rho的时候随机化就取120往下走了

#include <cstring>
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <algorithm>
using namespace std;

long long gcd( long long x,long long y ) { return y == 0 ? x : gcd( y,x % y ); }
long long fast_mul(  long long x,long long y,long long mod ) {
    long long tmp = 0,BASE = x;
    while( y ) {
        if( y & 1 ) tmp = ( tmp + BASE ) % mod;
        BASE = ( BASE + BASE ) % mod;
        y >>= 1; 
    }
    return tmp;
}

long long fast_pow( long long x,long long mod ) {
    long long BASE = x,tmp = 1;
    while( y ) {
        if( y & 1 ) tmp = fast_mul( tmp,BASE,mod );
        y >>= 1;
        BASE = fast_mul( BASE,mod );
    }
    return tmp;
}

bool miller_rabin( long long n ) {
    if( n == 2 || n == 3 || n == 5 || n == 7 || n == 11 || n == 13 ) return true;
    if( n % 2 == 0 || n % 3 == 0 || n % 5 == 0 || n % 7 == 0 || n % 11 == 0 || n % 13 == 0 ) return false;
    long long k = 0,d = n - 1;
    while ( d & 1 == 0 ){ d >>= 1; k++; }
    for( register int i = 1; i <= 10; i++ ) {
        long long x = rand() % ( n - 3 ) + 2 ;
        x = fast_pow( x,d,n );
        long long pre = x;
        for( register int j = 1; j <= k; j++ ) {
            x = fast_mul( x,x,n );
            if( x == 1 && pre != 1 && pre != n - 1 ) return false;
            pre = x;
        }
        if( x != 1 ) return false; 
    }
    return true;
}

long long pollard_rho( long long n,long long c ) {
    long long k = 2,i = 1;
    long long x = rand() % n + 3;
    long long y = x;
    while( 1 ) {
        i++;
        x = ( fast_mul( x,n ) + c ) % n ;
        long long d = gcd( ( y - x + n ) % n,n );
        if( d != 1 && d != n ) return d;
        if( x == y ) return n;
        if( i == k ){
            y = x;
            k <<= 1;
        }
    }
} 

long long prime[200],tail,cnt,num[200];

void find( long long n ) {
    if( n == 1 ) return;
    if( miller_rabin( n ) ) {
        prime[ tail++ ] = n;
        return ;
    }
    long long c = 120;
    long long p;
    while( ( p = pollard_rho( n,c-- ) ) == n );

    find( p );
    find( n / p );
} 

void solve( long long n ) {
    tail = 0;
    find( n );
    sort( prime,prime + tail );
    num[0] = 1;
    int k = 1;
    for( register int i = 1; i < tail; i++ ) {
        if( prime[i] == prime[i - 1] ) num[ k - 1 ]++;
        else {
            num[k] = 1;
            prime[ k++ ] = prime[i];
        }
    }
    cnt = k;
}
long long ans;
int main() {int T;
    scanf( "%d",&T );
    while( T-- ) { long long n;
        scanf( "%lld",&n );
        solve( n );
        ans = 0;
        for( register int i = cnt - 1; i >= 0; i-- ) {
            long long tmp = 1;
            for( register int j = 0; j < num[i]; j++ ) 
                tmp *= prime[i];
            ans += tmp;
        } 
        if( cnt == 1 ) ans /= prime[0];
        printf( "%lld %lldn",ans );
    } 
    return 0;
}