poj2429 GCD & LCM Inverse 數論 大數分解以及找所有因子

GCD & LCM Inverse

Time Limit: 2000MS	Memory Limit: 65536K
Total Submissions: 7146	Accepted: 1303

Description

Given two positive integers a and b, we can easily calculate the greatest common divisor (GCD) and the least common multiple (LCM) of a and b. But what about the inverse? That is: given GCD and LCM, finding a and b.

Input

The input contains multiple test cases, each of which contains two positive integers, the GCD and the LCM. You can assume that these two numbers are both less than 2^63.

Output

For each test case, output a and b in ascending order. If there are multiple solutions, output the pair with smallest a + b.

Sample Input

3 60      

Sample Output

12 15      

Source

POJ Achilles

題意：給你兩個數的最大公約數和最小公倍數，叫你求這兩個數，并且使得這兩個數的和最小。

因為數很大，是以必須用Pollard_Rho來分解素因子，将n除掉最大公約數後就是求n'能分解成兩個互素的數的和了，是以把每個素因子當作一個整體來處理。

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <map>
#include <algorithm>
using namespace std;
typedef __int64 ll;
ll gcd(ll a,ll b)
{
	return (b==0)?a:gcd(b,a%b);
}
ll Mulmod(ll a,ll b,ll n)
{
    ll  exp = a%n, res = 0;
    while(b)
    {
        if(b&1)
        {
            res += exp;
            if(res>n) res -= n;
        }
        exp <<= 1;
        if(exp>n)
            exp -= n;

        b>>=1;
    }
    return res;
}

ll exp_mod(ll a,ll b,ll c)
{
	ll k = 1;
	while(b)
	{
		if(b&1)
			k = Mulmod(k,a,c);
		a = Mulmod(a,a,c);
		b>>=1;
	}
	return k;
}
bool Miller_Rabbin(ll n, ll times)
{
    if(n==2)return 1;
    if(n<2||!(n&1))return 0;

    ll a, u=n-1, x, y;
    int t=0;
    while(u%2==0){
        t++;
        u/=2;
    }
    srand(100);
    for(int i=0;i<times;i++)
    {
        a = rand() % (n-1) + 1;
        x = exp_mod(a, u, n);
        for(int j=0;j<t;j++)
        {
            y = Mulmod(x, x, n);
            if ( y == 1 && x != 1 && x != n-1 )
                return false; //must not
            x = y;
        }
        if( y!=1) return false;
    }
    return true;
}

ll Pollard_Rho(ll n,ll c)
{
	ll x,y,d,i=1,k=2;
	y = x = rand() % (n-1) + 1;
	while(1)
	{
		i++;
		x = (Mulmod(x,x,n) + c)%n;
		d = gcd((x-y+n)%n,n);
		if(d>1&&d<n)
			return d;
		if(x==y)
			return n;
		if(i==k)
		{
			k<<=1;
			y = x;
		}
	}
}
ll factor[200],cnt;
void Find_factor(ll n,ll c)
{
	if(n==1)
		return;
	if(Miller_Rabbin(n,6))
	{
		factor[cnt++] = n;
		return;
	}
	ll p = n;
	ll k = c;
	while(p>=n)
		p = Pollard_Rho(p,c--);
	Find_factor(p,k);
	Find_factor(n/p,k);
}
ll fac[1000];int s;
ll p,q,nn;
void dfs(ll count,int step)
{
    if(step==s)
    {
        if(count+nn/count<p)
        {
            p=count+nn/count;
            q=count;
        }
        return ;
    }
    ll sum;
    sum=fac[step];
    dfs(count*sum,step+1);
    dfs(count,step+1);
}
int main()
{
	ll m,n;
	while(scanf("%I64d%I64d",&m,&n)!=EOF)
	{
		cnt = 0;
		n/=m;
		nn=n;
		Find_factor(n,120);
		sort(factor,factor+cnt);
		s=0;
		fac[0]=factor[0];
		for(int i=1;i<cnt;i++)
		{
		    if(factor[i]!=factor[i-1]) {s++;fac[s]=factor[i];}
		    else fac[s]*=factor[i];
		}
		p=1000000000000000000LL;//本來放在外面定義，腦殘了
		dfs(1,0);
		ll ww=nn/q;
		if(q>ww) swap(q,ww);
		printf("%I64d %I64d\n",m*q,m*ww);
	}
}