UVa11889 - Benefit

题意：给出A，C，找出最小的C使得lcm(A,B)=C

思路：lcm=(a*b)/gcd,把等号两侧同时除以a得到lcm/a=b/gcd左侧是已知的，右侧的gcd是a的因子中的一个，直接枚举a的所有因子找到答案就行了。

 1 #include<math.h>
 2 #include<stdio.h>
 3 #include<algorithm>
 4
 5
 6 using namespace std;
 7
 8
 9 int gcd(int a ,int b)
10 {
11     return a % b == 0 ? b : gcd(b ,a % b);
12 }
13
14
15 int yz[10000] ,yzs;
16
17
18 int main ()
19 {
20     int a ,b ,c,cc ,i;
21     int t;
22     scanf("%d" ,&t);
23     while(t--)
24     {
25         scanf("%d %d" ,&a ,&c);
26         if(c % a)
27         {
28             printf("NO SOLUTION\n");
29             continue;
30         }
31         cc = c;
32         c = c / a;
33         int n = sqrt(a);
34         yzs = 0;
35         for(i = 1 ;i <= n ;i ++)
36         if(a % i == 0) yz[++yzs] = i ,yz[++yzs] = a / i;
37         sort(yz + 1 ,yz + yzs + 1);
38         int Ans = -1;
39         for(i = 1 ;i <= yzs ;i ++)
40         {
41             int now = yz[i];
42             b = c * now;
43             if(gcd(a ,b) == now)
44             {
45                 Ans = b;
46                 break;
47             }
48         }
49         if(Ans == -1)  printf("NO SOLUTION\n");
50         else printf("%d\n" ,Ans);
51     }
52     return 0;
53 }

View Code