您的位置: 首页  >  IT文章  >  poj2429 GCD & LCM Inverse 数论 大数分解以及觅所有因子

poj2429 GCD & LCM Inverse 数论 大数分解以及觅所有因子

分类: IT文章 • 2024-05-07 13:10:54
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);
	}
}


相关推荐