POJ 2429 GCD & LCM Inverse

http://poj.org/problem?id=2429

给GCD 和 LCM 求对应的两个数 a b 要求 a+b最小

因为lcm(a, b) = a*b * gcd(a, b)

所以可以得到 a*b = LCM / GCD

要求 a*b值最小只要让a b尽量接近就好

也就是搜索LCM / GCD 的最近接的两个因子由题目给的数据范围 long long可以完成

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <string.h>
 4 #include <queue>
 5 #include <algorithm>
 6 #include <math.h>
 7 #define READ() freopen("in.txt", "r", stdin);
 8 #define MAXV 2007
 9 #define MAXE 20007
10 #define INF 0x3f3f3f3f3f3f3f3f
11 using namespace std;
12 
13 long long gcd(long long a, long long b)
14 {
15     if (b == 0) return a;
16     else return gcd(b, a%b);
17 }
18 int main()
19 {
20     READ()
21     long long GCD, LCM;
22     while (~scanf("%lld%lld", &GCD, &LCM) )
23     {
24         long long ab = LCM / GCD;//得到a和b的质因数之积
25         for (long long i = int(sqrt(ab)); i >= 1; i-- )
26         {
27             bool found = false;
28             for (long long j = int(sqrt(ab))+1; j >= 1; j--)
29             {
30                 if (i * j < ab) break;
31                 else if (i * j == ab)
32                 {
33                     if (gcd(i, j) == 1)
34                     {
35                         cout << i*GCD << " " << j*GCD << endl;
36                         found = true;
37                     }
38                 }
39             }
40             if (found) break;
41         }
42     }
43     return 0;
44 }