poj2429专题

poj2429 GCD LCM Inverse 数论 质因数分解

题意:输入两个数分别为 c , d 找到最小的 a + b 使得 Gcd(a,b) = c ; Lcm(a,b) = d; 找到 这样 的 a 与 b ,使得 a+b最小,而且要让 a<=b. 分析: 令 gcd(a,b) = c ,lcm(a,b) = d. 分析gcd与lcm的性质,有 gcd(a,b) * lcm(a,b) = a * b; 也就是 c * d = a * b,等式两边同时除