题目链接：
https://cn.vjudge.net/problem/POJ-2429
题目大意：
给出两个数的gcd和lcm，求原来的这两个数（限定两数之和最小）。
解题思路：
首先，知道gcd和lcm求原来的两个数，需要分解lcm / gcd 。将其分解为互质的两个数。
首先将lcm/gcd质因数分解，要分解出沪互质两个数字，那么这两个数字的gcd=1，也就是没有公共的质因子，所以可以直接枚举这两个数字的质因子，如果一个数要取这个质因子，就把它的指数全部取掉。
质因数分解用大数因式分解来做。
分成两个互质的数字可以用二进制枚举子集，1表示取这个质因数，0表示不取，最终求出最小的和的两个数。
#include<iostream>
#include<ctime>
#include<algorithm>
#include<map>
#define INF 1000000000000000009
using namespace std;
typedef long long ll;
map<ll, int>m;
const int mod = ;
const int times = ;//测试50次
ll mul(ll a, ll b, ll m)
//求a*b%m
{
ll ans = ;
a %= m;
while(b)
{
if(b & )ans = (ans + a) % m;
b /= ;
a = (a + a) % m;
}
return ans;
}
ll pow(ll a, ll b, ll m)
//a^b % m
{
ll ans = ;
a %= m;
while(b)
{
if(b & )ans = mul(a, ans, m);
b /= ;
a = mul(a, a, m);
}
ans %= m;
return ans;
}
bool Miller_Rabin(ll n, int repeat)//n是测试的大数，repeat是测试重复次数
{
if(n == || n == )return true;//特判
if(n % == || n == )return false;//偶数和1 //将n-1分解成2^s*d
ll d = n - ;
int s = ;
while(!(d & )) ++s, d >>= ;
//srand((unsigned)time(NULL));在最开始调用即可
for(int i = ; i < repeat; i++)//重复repeat次
{
ll a = rand() % (n - ) + ;//取一个随机数,[2,n-1)
ll x = pow(a, d, n);
ll y = ;
for(int j = ; j < s; j++)
{
y = mul(x, x, n);
if(y == && x != && x != (n - ))return false;
x = y;
}
if(y != )return false;//费马小定理
}
return true;
}
ll gcd(ll a, ll b)
{
return b == ? a : gcd(b, a % b);
}
ll pollard_rho(ll n, ll c)//找到n的一个因子
{
ll x = rand() % (n - ) + ;
ll y = x, i = , k = ;
while()
{
i++;
x = (mul(x, x, n) + c) + n;//不断调整x2
ll d = gcd(y - x, n);
if( < d && d < n)
return d;//找到因子
if(y == x)
return n;//找到循环，返回n，重新来
if(i == k)//一个优化
{
y = x;
k <<= ;
}
}
}
void Find(ll n, ll c)
{
if(n == )return;//递归出口 if(Miller_Rabin(n, times))//如果是素数，就加入
{
m[n]++;
return;
} ll p = n;
while(p >= n)
p = pollard_rho(p, c--);//不断找因子，知道找到为止，返回n说明没找到 Find(p, c);
Find(n / p, c);
}
ll pow2(ll a, ll b)
{
ll ans = ;
while(b)
{
if(b & )ans *= a;
b /= ;
a *= a;
}
return ans;
}
int main()
{
ll x, y;
ll a[], b[];
//srand((unsigned)time(NULL));
while(cin >> x >> y)
{
m.clear();
y = y / x;
Find(y, );//这是自己设置的一个数
map<ll, int>::iterator it = m.begin();
for(int i = ; it != m.end(); it++, i++)
{
a[i] = it->first;
b[i] = it->second;
}
ll Max = INF, ansa, ansb;
int t = m.size();
for(int i = ; i < (<<t); i++)
{
ll tot = ;
for(int j = ; j < t; j++)
{
if(i & (<<j))
tot *= pow2(a[j], b[j]);
}
ll cnt = tot + y / tot;
if(cnt < Max)
{
Max = cnt;
ansa = tot;
ansb = y / tot;
}
}
if(ansa > ansb)swap(ansa, ansb);
cout<<ansa*x<<" "<<ansb*x<<endl;
}
return ;
}