3 60

12 15

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top

题意：给你两个数的gcd和lcm，让你求这两个数

题解：我们考虑lcm/gcd，这样得出的两个数一定是互质的。

然后我们考虑分解质因数，两个互质的数一定没有公因数，因此dfs暴力其中一个数的因数即可。

数很大，无法直接暴力分解因数，这里采用Pollard-rho算法分解（不知道的自行百度）

然后怎么保证a+b最小呢，其实两个数最接近时，这两个数的和一定最小（可以证明的）。

呢我们直接dfs即可。

#include<set>      
#include<map>         
#include<stack>                
#include<queue>                
#include<vector>        
#include<string>     
#include<time.h>    
#include<math.h>                
#include<stdio.h>                
#include<iostream>                
#include<string.h>                
#include<stdlib.h>        
#include<algorithm>       
#include<functional>        
using namespace std;                
#define ll long long          
#define inf 1000000000           
#define Mod 10007                
#define maxn  50500    
#define lowbit(x) (x&-x)                
#define eps 1e-9   
ll cnt, fat[101],mx,ans;
ll pri[2550005], a[2550005] = {1,1};
ll Multi(ll a, ll b, ll mod)        //和上面一样，但比上面慢很多 
{ 
    ll ans = 0; 
    a %= mod; 
    while(b) 
    { 
        if(b%2==1)  ans = (ans+a)%mod, b--; 
        else  a = (a+a)%mod, b /= 2; 
    } 
    return ans; 
} 
ll Pow(ll a, ll b, ll mod)  
{  
    ll ans = 1;  
    a %= mod;  
    while(b)  
    {  
        if(b&1)  ans = Multi(ans, a, mod), b--;  
        else  a = Multi(a, a, mod), b /= 2;  
    }  
    return ans;  
}  
ll Gcd(ll a, ll b)  
{ 
	if(b==0)
		return a;
	return Gcd(b, a%b);
}  
int Miller_Rabin(ll n)  
{  
    int i, j, k;  
    ll a, x, y, mod;  
    if(n==2)  return 1;  
    if(n<2 || n%2==0)  return 0;  
    k = 0, mod = n-1;  
    while(mod%2==0)  
    {  
        k++;  
        mod /= 2;  
    }  
    for(i=1;i<=15;i++)  
    {  
        a = rand()%(n-1)+1;  
        x = Pow(a, mod, n);  
        y = 0;  
        for(j=1;j<=k;j++)  
        {  
            y = Multi(x, x, n);  
            if(y==1 && x!=1 && x!=n-1)  
                return 0;  
            x = y;  
        }  
        if(y!=1)  
            return 0;  
    }  
    return 1;  
}  
ll Divi(ll n)  
{  
    ll i, k, x, y, p, c;  
    if(n==1)  
        return 1;  
    k = 2, p = 1;  
    y = x = rand()%n, c = rand()%(n-1)+1;  
    for(i=1;p==1;i++)
    {
        x = (Multi(x, x, n)+c)%n;
		p = x-y;
		if(p<0)
			p = -p;
        p = Gcd(n, p);  
        if(i==k)  
            y = x, k *= 2;  
    }
    return p;  
}  
void Pollard_rho(ll n)  
{  
    ll p;  
    if(n==1)  
        return;  
    if(Miller_Rabin(n))  
        fat[++cnt] = n;  
    else  
    {  
        p = Divi(n);
		Pollard_rho(p);  
        Pollard_rho(n/p);  
    }  
}  
void dfs(ll x,ll y)
{
	if(x>cnt)
	{
		if(y>ans && y<=mx)
			ans=y;
		return;
	}
	dfs(x+1,y);
	dfs(x+1,y*fat[x]);
}
int main(void)
{
	ll a,b;
	while(scanf("%lld%lld",&a,&b)!=EOF)
	{
		cnt=0;b=b/a;
		Pollard_rho(b);
		sort(fat+1,fat+cnt+1);
		int i,j=1;
		for(i=2;i<=cnt;i++)
		{
			while(fat[i]==fat[i-1] && i<=cnt)
				fat[j]*=fat[i],i++;     
			if(i<=cnt)
				fat[++j]=fat[i];
		}   
		cnt=j;ans=1;
		mx=(ll)sqrt((double)b);
		dfs(1ll,1ll);
		printf("%lld %lld\n",ans*a,b/ans*a);
	}
	return 0;
}