GCD & LCM Inverse

wohenlaoshia

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 原题出自http://acm.pku.edu.cn/JudgeOnline/problem?id=2429 发现这里都是大牛，这个会不会太简单了呀，，不要鄙视我T_T,偶刚搞ACM不久~~ 已知a,b的最大公约数GCD和最小公倍数LCM，如何求a,b?如有多组解，则输出a+b和为最小的那组解,限定时间在2S内，由于给出的数值范围达到64位，基本方法是先将LCM/GCD,再把该值拿去分解成两数相乘，可是我写的总是超时，我是先通随机算法判断出LCM/GCD是否为素数，如是则直接判断出答案，否则还是要把LCM/GCD拿去分解，不知有没有什么好的算法。

liangbch

n1=3; //GCD n2=60; //LCM n1*x*y=n2; ->x*y=n2/n1; 分解n2/n1为x,y. 约束条件 GCD(x,y)=1; GCD(x,n1)=1; GCD(y,n1)=1; a=n1*x; b=n1*y; 此题关键是将一个数分解成为2个数的乘积，且分解后的两个数互质。 未经详细分析，不知道我说的是否正确。

wohenlaoshia

嗯，的确如此，但由于sqrt(LCM/GCD)可能达到2^32,如何高效分解，是个问题

wohenlaoshia

如若从i <- sqrt(LCM/GCD) to 1逐个遍历，得到的第一组不相等的可行解，应该就是答案，但这样速度远远达不到2S之内的要求

mathe

主要就是因子分解问题,小因子可以采用试除的方法,而是否素数可以采用素数测试.但是如果含有两个大因子,还是比较难的,看来你需要学习一下二次筛选法等比较高级一点的因子分解方法

wohenlaoshia

在google上查了一下，貌似很难找到相关文档，不知哪里有相关的学习资料

mathe

你在论坛里面找一找，无心人应该找到不少因子分解方面的程序，很多都是带源代码的。（当然这些代码会很复杂）

mathe

还有The Art of Computer Programming里面也介绍了几种因子分解方法，对付这个题目应该可以了

无心人

这个还是用费马分解算法吧 另外，暴力分解也能在2s内完成吧 考虑用6k + 1, 6k + 5的整数除

mathe

暴力分解可能有点问题，因为我们需要计算$2^32$以内的所有素数，这个就有点问题。还有通常使用的测试数据应该不只有一组。