传送门：
GCD & LCM Inverse
GCD & LCM Inverse
|
Source : HUST Monthly Contest of April |
|||
|
Time limit : 2 sec |
Memory limit : 32 M |
||
Submitted
: 761,
Accepted
: 213
We are all familiar with the Euclid’s algorithm. Given two positive integers a, b. we can easily find the greatest common divisor (GCD) and least common multiple (LCM) of a, b through this method. But what about the inverse? That is: given GCD and LCM of a and b, can you find a, b ?
Input
The input will contain multiple test cases, each of which contains two positive integers: GCD and LCM. You can safely assume these integers will be less than 2^63-1.
Output
For each test case, output a, b in ascending order. If there are multiple solutions, output the pair with smallest a+b.
Sample Input
3 60
Sample Output
12 15
LangLang @ Achilles Team
解题报告：
题意：已知两个数的gcd和lcm求这两个数a, b，多解时要求a+b最小
思路：a/gcd * b/gcd = lcm/gcd，还有一个常识性质的性质：a*b为定值时，a和b相差越小，a+b越小。所以从lcm/gcd的平方根开始枚举a即可。
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
long long gcd (long long a,long long b){
return b==0?a:gcd(b,a%b);
}
int main(){
long long a,b;
while(scanf("%lld%lld",&a,&b)==2){
long long tmp=b/a,i;
for(i=sqrt(1.0*tmp);i>=1;i--)
if(tmp%i==0){
b=tmp/i;
if(gcd(i,b)==1)
break;
}
printf("%lld %lld\n",a*i,a*b);
}
return 0;
}