3095006_wa.cpp

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

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

using namespace std;

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 cnt;
ll newnum[20];
int mark[20];
ll gcd , lcm, bak, ans, small, big;

void dfs(int p,ll nn)
{
	int i;

	if(p==cnt)
	{
		if(ans == -1 || gcd * (nn + bak/nn) < ans)
		{
			ans = gcd * (nn + bak / nn);
			small = gcd * (nn > bak / nn? bak / nn : nn);
			big = ans - small;
		}
		return ;
	}
	dfs(p+1,nn);
	dfs(p+1,nn*newnum[p]);
}

int main()
{
    
    int nCase, j, i;
    ll num;
	
    while (scanf("%I64d%I64d", &gcd,&lcm)==2)
    {
		if(gcd == lcm)
		{
			printf("%I64d %I64d\n",gcd,lcm);
			continue;
		}
		num = lcm / gcd;
		bak = num;
        if ( Miller_Rabin(num, MAX_COUNT) == 1 )
        {
            printf("%I64d %I64d\n",gcd,gcd*num);
        }
        else
        {
			Fac[ 0 ] = 0;
            if ( num % 2 == 0 ) {
                 Fac[0] = 1;
				 Fac[1] = 1;
                 while(num%2==0)
				{
					 Fac[1] *= 2;
					 num /= 2;
				 }
            }
			if(num!=1)
            FindFac(num);
			sort(&Fac[1],&Fac[1]+Fac[0]);
			cnt = 0;
            for (i = 1; i <= Fac[ 0 ]; i++)
            {
				j = i;
				ll tt = 1;
				while(j <= Fac[0]&&Fac[j]==Fac[i])
				{
					j++;
					tt *= Fac[i];
				}
				newnum[cnt++] = tt;
            }
			ans = -1;
			dfs(0,1);
			printf("%I64d %I64d\n",small,big);
        }        
    }
   
	return 0;
}