GCD and LCM
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Others)
Total Submission(s): 2977 Accepted Submission(s): 1302
Problem Description
Given two positive integers G and L, could you tell me how many solutions of (x, y, z) there are, satisfying that gcd(x, y, z) = G and lcm(x, y, z) = L?
Note, gcd(x, y, z) means the greatest common divisor of x, y and z, while lcm(x, y, z) means the least common multiple of x, y and z.
Note 2, (1, 2, 3) and (1, 3, 2) are two different solutions.
Note, gcd(x, y, z) means the greatest common divisor of x, y and z, while lcm(x, y, z) means the least common multiple of x, y and z.
Note 2, (1, 2, 3) and (1, 3, 2) are two different solutions.
Input
First line comes an integer T (T <= 12), telling the number of test cases.
The next T lines, each contains two positive 32-bit signed integers, G and L.
It’s guaranteed that each answer will fit in a 32-bit signed integer.
The next T lines, each contains two positive 32-bit signed integers, G and L.
It’s guaranteed that each answer will fit in a 32-bit signed integer.
Output
For each test case, print one line with the number of solutions satisfying the conditions above.
Sample Input
2
6 72
7 33
6 72
7 33
Sample Output
72
0
0
Source
Recommend
liuyiding
这是一道好题。
我是看题解才会的：https://www.cnblogs.com/fightfor/p/3960212.html
思路
将满足条件的一组x,z,y都除以G,得到x‘，y',z',满足条件gcd(x',y',x') = 1,同时lcm(x',y',x') = G/L.
特判，当G%L ！= 0 时，无解。
然后素数分解G/L，假设G/L = p1^t1 * p2^t2 *````* pn^tn。
满足上面条件的x,y,z一定为这样的形式。
x' = p1^i1 * p2^i2 *```* pn^in.
y' = p1^j1 * p2^j2 * ```*pn^jn.
z' = p1^k1 * p2^k2 * ```*pn^kn.
为了满足上面的条件，对于p1,一定有max(i1,j1,k1) = t1.min(i1,j1,k1) =0;则当选定第一个数为0，第二个数为t1时，第三个数可以为0-t1，又由于有顺序的，只有(0,t1,t1) 和(0,t1,0)这两种情形根据顺序只能产生三种结果，其他的由于三个数都不一样，一定能产生6种，所以最后产生了6*（t1-1）+3*2 = 6*t1种，根据乘法原理以及关于素数分解的唯一性，反过来，素数组合必然也是唯一的数，一共有6*t1 * 6*t2 *`````*6*tn种选法。
特判，当G%L ！= 0 时，无解。
然后素数分解G/L，假设G/L = p1^t1 * p2^t2 *````* pn^tn。
满足上面条件的x,y,z一定为这样的形式。
x' = p1^i1 * p2^i2 *```* pn^in.
y' = p1^j1 * p2^j2 * ```*pn^jn.
z' = p1^k1 * p2^k2 * ```*pn^kn.
为了满足上面的条件，对于p1,一定有max(i1,j1,k1) = t1.min(i1,j1,k1) =0;则当选定第一个数为0，第二个数为t1时，第三个数可以为0-t1，又由于有顺序的，只有(0,t1,t1) 和(0,t1,0)这两种情形根据顺序只能产生三种结果，其他的由于三个数都不一样，一定能产生6种，所以最后产生了6*（t1-1）+3*2 = 6*t1种，根据乘法原理以及关于素数分解的唯一性，反过来，素数组合必然也是唯一的数，一共有6*t1 * 6*t2 *`````*6*tn种选法。
附ac代码：
1 #include <cstdio>
2 #include <cstring>
3 #include <iostream>
4 #include <algorithm>
5 #include <cmath>
6 using namespace std;
7 typedef long long ll;
8 const int maxn = 1111111;
9 int nu[maxn];
10 int isprim[maxn];
11 int prim[maxn];
12 int main()
13 {
14 int t;
15 int g,l;
16 scanf("%d",&t);
17 while(t--)
18 {
19 scanf("%d%d",&g,&l);
20 if(l%g!=0)
21 {
22 printf("0\n");
23 continue;
24 }
25 memset(nu,0,sizeof(nu));
26 int cnt=0;
27
28 int m=l/g;
29 int sqm=sqrt(m+1);
30 for(int i=2;i<=sqm;++i)
31 {
32 if(m%i==0)
33 {
34 ++cnt;
35 while(m%i==0)
36 {
37 nu[cnt]++;
38 m/=i;
39 }
40 }
41
42 }ll sum=1;
43 if(m!=1)
44 sum=6;
45
46 for(int i=1;i<=sqm;++i)
47 {
48 if(nu[i]!=0)
49 sum*=nu[i]*6;
50 }
51 printf("%lld\n",sum);
52 }
53 return 0;
54 }