本文共 1620 字，大约阅读时间需要 5 分钟。

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.

 

 

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.

 

 

Output

For each test case, print one line with the number of solutions satisfying the conditions above.

 

 

Sample Input

2

6 72

7 33

 

 

Sample Output

72

0

代码及注释如下：

 

/*此题的G和L范围在int范围内,所以求其中的最大素因子不超过100000;所以第一步需要求出1-10万中的素数,然后储存到vector数组中...第二步就是求个数了..如果LCM不能除尽GCD的话,说明不能组成,直接输出0.如果能够除尽,L需要先除以G,将两个数的公共素因子幂全部消去...最后是素因子分解L.每分解一个素因子就用6*素因子的指数....答案就是素因子的指数乘6累成起来的...*/#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;const int maxn=100000;vector
        
         pri;int isnot[maxn+5];int t;int x,y;int Size;void Judge (){ memset (isnot,0,sizeof(isnot)); isnot[1]=1; for (int i=2;i<=maxn;i++) { if(!isnot[i]) { pri.push_back(i); for (int j=2*i;j<=maxn;j+=i) isnot[j]=1; } } Size=pri.size();}int main(){ Judge(); scanf("%d",&t); while (t--) { int num=1; scanf("%d%d",&x,&y); if(y%x) printf("0\n"); else { y/=x; for (int i=0;i
         
          y) break; while(y%pri[i]==0) { cnt++; y/=pri[i]; } if(cnt) num*=6*cnt; } if(y!=1) num*=6; printf("%d\n",num); } } return 0;}
         
        
       
      
     
    
   

 

转载地址：http://zaaen.baihongyu.com/