3094860_ac_1499ms_152k.c

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <stdlib.h>
typedef __int64 ll;
ll Fac[64], time = 12983;
const int MAX_COUNT = 32;

ll PowerMod(ll a, ll b, ll n)
{

    ll back = 0, temp = a % n;
    b %= n;
    while ( b > 0 )
    {
        if ( b & 1 )
            back = (back + temp) % n;
        temp = (temp<<1) % n;
        b >>= 1; 
    }
    return back;
}


ll ExpMod(ll a, ll b, ll n)
{
    ll d;		       
    
    if ( b == 1 ) return a;
    if ( b % 2 ){
         d = ExpMod( a, b / 2, n );
         d = PowerMod( d, d, n );
         d = PowerMod( a, d, n );   
    } else {
         d = ExpMod( a, b / 2, n );
         d = PowerMod( d, d, n );         
    }

    return d;
}

ll Gcd(ll a, ll b)
{
    ll c;
    a = a < 0 ? -a : a;
    c = a % b;
    while ( c ){
          a = b;
          b = c;
          c = a % b;      
    }   
	return b;
}

int Prime( ll a, ll n ){
    ll u = n - 1, x0, x1;
    int m = 0, i;
    while ( u % 2 == 0 ){
          u /= 2;
          m++;      
    }
    x0 = ExpMod( a, u, n );
    for ( i = 0; i < m; i++ ){
        x1 = PowerMod( x0, x0, n );
        if ( x1 == 1 && x0 != 1 && x0 != n - 1 ){
             return 0;   
        }
        x0 = x1;
    }
    if ( x1 != 1 ) return 0;
    return 1;

}

int Miller_Rabin(ll n, int count) 
{
    int i;
    ll a;
    if ( n == 1 )
        return 0; 
    if ( n == 2 )
        return 1;    

    for ( i = 1; i <= count; i++)
    {
        time += 121;
        srand( time );
        a = rand() % (n-1) + 1;
        if ( Prime(a, n) == 0 )
            return 0;
    }
   
    return 1;
}

ll Pollard_Rho(ll num)
{
    ll i = 1, k = 2, c;
    ll x;
    ll y, d;
    
    do{
       time += 251;
       srand( time );
       c = rand()%(num-1)+1;   
    }while ( c == 0 || c == 2 );
    
    time += 169;
    srand( time );
    x = rand() % ( num - 1 ) + 1;
    y = x;
    if ( c == 2 ) c++;
    do
    {
        i++;
        x = (PowerMod(x, x, num) + num - c ) % num;
        if ( x == y )
            break;
        d = Gcd( y - x , num);
        if ( d > 1 && d < num )
            return d;
        if ( i == k )
        {
            y = x;
            k *= 2;
        }
    }while ( 1 );
    return num;
}

void FindFac( ll num )
{
    ll factor, r = 0;
    if ( Miller_Rabin(num, MAX_COUNT) == 1 )
    {
        Fac[ 0 ] ++;
        Fac[ Fac[ 0 ] ] = num;
        return;
    }
    
    do
    {
        factor = Pollard_Rho(num);   
    }while ( factor == num );
    FindFac(factor);
    FindFac(num/factor);
}

int main()
{
    
    int nCase, i;
    ll num, minAns;
    scanf("%d", &nCase);
    while ( nCase -- )
    {
        scanf("%I64d", &num);
        if ( Miller_Rabin(num, MAX_COUNT) == 1 )
        {
            printf("Prime\n");
        }
        else
        {
            if ( num % 2 == 0 ) {
                 printf("2\n");
                 continue;  
            }
            Fac[ 0 ] = 0;
            FindFac(num);
            minAns = num;
            for (i = 1; i <= Fac[ 0 ]; i++)
            {
                if ( Fac[i] < minAns )
                    minAns = Fac[i];
            }
            printf("%I64d\n", minAns);
        }        
    }
   
	return 0;
}