3094909_re.cpp

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

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>

using namespace std;

typedef __int64 ll;
ll Fac[640], 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 ( num == 2 || Miller_Rabin(num, MAX_COUNT) == 1 )
    {
        Fac[ 0 ] ++;
		if(Fac[0] > 100)
			while(1) puts("Love u");
        Fac[ Fac[ 0 ] ] = num;
        return;
    }
    
    do
    {
        factor = Pollard_Rho(num);   
    }while ( factor == num );
    FindFac(factor);
    FindFac(num/factor);
}

int main()
{
    
    int nCase, j, i;
    ll num, bak;
    ll gcd, lcm;
    
    while ( scanf("%I64d%I64d",&gcd,&lcm)==2)
    {
          num = lcm / gcd;
		  bak = num;
        if ( Miller_Rabin(num, MAX_COUNT) == 1 )
        {
            printf("%I64d %I64d\n",gcd,gcd*num);
        }
        else
        {
            Fac[ 0 ] = 0;
            FindFac(num);
            sort(&Fac[1],&Fac[1]+Fac[0]);
			ll newnum[200], cnt;
			cnt = 0;
			for(i = 1; i <= Fac[0]; i++)
			{
				j = i;
				newnum[cnt] = 1;
				while(j <= Fac[0] && Fac[j]==Fac[i])
				{
					newnum[cnt] *= Fac[i];
					j++;
				}
				cnt++;
				i = j-1;
			}
			if(cnt > 15)
			{
				while(1)
				{
					puts("I love you");
				}
			}
			int max, l;
			const int expr[] = {1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536};
			ll ans, small, big, tmp;
			max = 1 << cnt;
			ans = -1;
			for(j = 0; j < max; j++)
			{
				tmp = 1;
				for(l = 0; l < cnt; l++)
				{
					if((expr[l] & j) != 0)
					{
						tmp *= newnum[l];
					}
				}
				if(ans == -1 || gcd * (tmp + bak / tmp) < ans)
				{
					ans = (tmp + bak / tmp) * gcd;
					small = tmp * gcd;
					big = bak / tmp * gcd;
					if(small > big)
					{
						tmp = small;
						small = big;
						big = tmp;
					}
				}
			}
			printf("%I64d %I64d\n",small,big);

        }        
    }
   
	return 0;
}