题意：给出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 }