2015
07-17

# GCD and LCM

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.

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.

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.

2
6 72
7 33 

72
0

题解：已知x%g=y%g=z%g=0，l%x=l%y=l%z=0,所以l%g=0。这个可以判定是否存在(x,y,z)符合条件。

x/g=p1^b1*p2^b2*…*pk^(bk)；同理得到y/g,z/g，指数为ci和di.

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int T;
cin>>T;
while(T--)
{
int g,l,i,j,k,t,n,m,ans=1;
cin>>g>>l;
if(l%g!=0){cout<<0<<endl;continue;}//不成立条件
n=l/g;
m=(int)sqrt(n+0.5);
for(i=2;i<=m;i++)
{
if(n%i==0)
{
t=0;
while(n%i==0)
{
n=n/i;
t++;
}
ans*=(t+1)*(t+1)*(t+1)-2*t*t*t+(t-1)*(t-1)*(t-1);//容斥原理
}
}
if(n>1)
ans*=6;//指数为1
cout<<ans<<endl;
}
return 0;
}