hdu 4497 GCD and LCM

思路：易知L不能整除G时为0；

将L/G质因数分解，对于其中的因子p,个数为cnt，则至少有一个包含p^cnt,至少有一个数不包含p；

只有一个数包含p^cnt时，有C(3,1);

有2个数包含p^cnt时，有C(3,1);

有2个数包含p因子，其中一个是p^cnt,另外一个有cnt-1种，总共有(cnt-1)A(3,2).

所以总共有6*cnt。

代码如下：

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<algorithm>
 4 #include<iomanip>
 5 #include<cmath>
 6 #include<cstring>
 7 #include<vector>
 8 #define ll __int64
 9 #define pi acos(-1.0)
10 #define MAX 50000
11 using namespace std;
12 int prime[MAX],cnt,e[MAX],lena;
13 bool f[MAX];
14 void init()
15 {
16     int i,j;
17     cnt=0;
18     for(i=2;i<MAX;i++){
19         if(f[i]==0) prime[cnt++]=i;
20         for(j=0;j<cnt&&i*prime[j]<MAX;j++){
21             f[i*prime[j]]=1;
22             if(i%prime[j]==0) break;
23         }
24     }
25 }
26 int solve(int n)
27 {
28     int i,j=0,ans=1;
29     for(i=0;i<cnt&&prime[i]*prime[i]<=n;i++){
30         if(n%prime[i]==0){
31             e[j]=1;
32             n/=prime[i];
33             while(n%prime[i]==0){
34                 e[j]++;
35                 n/=prime[i];
36             }
37             j++;
38         }
39     }
40     if(n>1){
41         e[j++]=1;
42     }
43     for(i=0;i<j;i++){
44         ans*=6*e[i];
45     }
46     return ans;
47 }
48 int main(){
49     int i,t,n,a,b,j,ans;
50     init();
51     scanf("%d",&t);
52     while(t--){
53         scanf("%d%d",&a,&b);
54         if(b%a) printf("0
");
55         else  printf("%d
",solve(b/a));
56     }
57     return 0;
58 }

View Code