UVA11388 GCD LCM
UVA11388 GCD LCM
（链接点这儿）
题目：
The GCD of two positive integers is the largest integer that divides both the integers without any remainder. The LCM of two positive integers is the smallest positive integer that is divisible by both the integers. A positive integer can be the GCD of many pairs of numbers. Similarly, it can be the LCM of many pairs of numbers. In this problem, you will be given two positive integers. You have to output a pair of numbers whose GCD is the first number and LCM is the second number.
Input The first line of input will consist of a positive integer T. T denotes the number of cases. Each of the next T lines will contain two positive integer, G and L. Output For each case of input, there will be one line of output. It will contain two positive integers a and b, a ≤ b, which has a GCD of G and LCM of L. In case there is more than one pair satisfying the condition, output the pair for which a is minimized. In case there is no such pair, output ‘-1’. Constraints • T ≤ 100 • Both G and L will be less than 231 .
Sample Input 2 1 2 3 4
Sample Output 1 2 -1
两个正整数的 GCD 是除除两个整数而不不产生任何余数的最大整数。两个正整数的 LCM 是被两个整数整除的最小正整数。正整数可以是许多数字对的 GCD。同样,它可以是许多对数字的LCM。在此问题中,您将获得两个正整数。您必须输出一对 GCD 是第一个数字,LCM 是第二个数字的一对数字。
输入的第一行将由正整数 T. T 表示案例数。下一个 T 行将包含两个正整数,G 和 L 输出 对于每个输入情况,将有一个输出行。它将包含两个正整数 a 和 b, a = b, 其 GCD 为 G, LCM 为 L。如果有多个对满足条件,则输出最小化的对。如果没有这样的对,输出”-1″。约束 = T = 100 = G 和 L 将小于 231 。
样本输入 2 1 2 3 4
样品输出 1 2 -1
（草率的中文翻译）
先上代码！
1 #include<bits/stdc++.h> 2 using namespace std; 3 int t; 4 long long a,b,c,d,ans[101][3]; 5 int main() 6 { 7 cin>>t; 8 for(int i=1;i<=t;i++) 9 { 10 cin>>a>>b; 11 if(b%a==0)//如果GCD可被LCM整除 12 { 13 ans[i][1]=a; 14 ans[i][2]=b; 15 continue; 16 } 17 else ans[i][1]=-1; 18 } 19 for(int i=1;i<=t;i++) 20 if(ans[i][1]==-1) 21 printf("-1\n"); 22 else 23 printf("%lld %lld\n",ans[i][1],ans[i][2]); 24 return 0; 25 }
为什么可以这么写呢？下面我详细讲一讲：
证明：
我们先看到第11行的if语句：当GCD可被LCM整除时，两个数为GCD和LCM。
我们设两个数分别为a，b。（a<=b）
首先我们知道，GCD一定可以被a和b整除，而a和b又可以被LCM整除，所以GCD一定可被LCM整除。
而我们又知道，当一个数x可被y整除时，他们的GCD为x，LCM为y。
所以当a=GCD（a,b），b=LCM(a,b)时，(a,b)这对数一定为一组解。
又因为GCD=a*k(k>=1&&k==int(k))，所以GCD>=a，最小值为a。
所以这里的a为最小值。
我们确定了a为最小值以后，又根据公式：GCD*LCM=a*b，其中GCD，a，LCM已知，所以b一定是固定的，而且就等于LCM。
所以当a=GCD(a,b)，b=LCM(a,b)时，（a,b）为符合要求的最优解。
证毕。
第11行证完了之后，我们再来证第17行的else语句。
其实还是利用GCD一定可以被a和b整除，而a和b又可以被LCM整除，所以GCD一定可被LCM整除这个原理。
所以一定无解。
证毕。
这个时候我们就证完了。O(t)算法。
（其实如果你要变成O(1)算法，只需要输入一个，再输出一个。只是本人不习惯这样而已）
如果你觉得你有更巧妙的方法，欢迎在下方留言。