C - （例题）整数分解，计数

Crawling in process... Crawling failed Time Limit:1000MS     Memory Limit:65535KB     64bit IO Format:%I64d & %I64u

Submit

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

题目大意：

给你两个数L,G，问你有多少有序数组（x,y,z)满足GCD（x,y,z)=G,LCM(x,y,z)=L,首先如果gcd(x,y,z)=G,

那么有gcd(x/G,y/G,z/G)=1（说明这三个数两两互素），此时应该满足lcm(x,y,z)=L/G,要求L/G为整数，则若L%G==0，则一定有解，(x,y,z都等于L/G即可）

反之无解

此时将L/G作正整数唯一分解，T=L/G=a1^b1*a2^b2*.......*an^bn，对于a1，要满足gcd(x/g,y/g,z/g)=1，a1^k则至少有一个k=0,同时

还得满足lcm(x/g,y/g,z/g)=l/g,则至少有一个k=b1，这样就有三种情况（0，0，b1)(b1,b1,0)(0,1~b1-1,b1)共有6+6（b1-1)=6*b1种，其他的同理

由分步乘法计数原理，最终答案为(6*b1)*(6*b2)*........(6*bn)

代码：

#include 
       
        #include 
        
         #include 
         
          #include
          
           #include 
           
            using namespace std;typedef long long ll;const int maxn=2e5;//bool vis[maxn];ll prime[maxn/10];int tot;void getprime()//因为n的范围是1e14，打表只需要打到sqrt(n)即可，最多只可能有一个素因子大于sqrt(n)，最后特判一下即可；{    memset(vis,true,sizeof(vis));    tot=0;    for(ll i=2;i