GCD and LCM

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65535/65535 K (Java/Others)
Total Submission(s): 2234    Accepted Submission(s): 986

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
 

Source

2013 ACM-ICPC吉林通化全国邀请赛——题目重现 


思路：

这道题的题意是给出三个数的最大公约数和最小公倍数，求满足这两个条件的三个数有多少种组合。方法就是运用质因数分解，假设三个数a.b,c，因为最小公倍数=a*b*c/最大公约数/最大公约数，所以最大公约数和最小公倍数之间可以有一些特殊的关系。最小公倍数一定是最大公约数的倍数，如果不是则说明无解。

这题要用唯一分解定理来做。gcd(x,y,x)=G,lcm(x,y,z)=L;
x=p1^a1*p2^a2……ps^as;
y=p1^b1*p2^b2……ps^bs;
z=p1^c2*p2^c2……ps^cs;
G,L已知，满足条件：
G=p1^min(a1,b1,c1)……ps^min(as,bs,cs)=p1^e1……ps^es
L=p1^max(a1,b1,c1)……ps^max(as,bs,cs)=p1^h1……ps^hs
则满足 ei=min(ai,bi,ci) hi=max(ai,bi,bi),考虑组合数。 


考虑有序数对，对于每个（ei,hi) ，先考虑位置，不考虑位置上的数的大小，让 (x,y,z)固定两个位置填数，让一个位置变化，位置的组合一共有 6种，即 A(3,2)=6。然后对每一种，考虑数字大小的组合，两个固定的位置填最大和最小值，剩下的那个位置填他们之间的数，每一种都有（hi-ei+1)种。比如从最小为2最大为6，则那个剩下的位置可以填2、3、4、5、6五种。


然后考虑重复情况，重复情况的原因是因为在固定两个位置放ei和hi之后，那个任意位置可以放ei到hi的任意数。就比如：

x y z   x y z
1 1 3
3 1 1
1 2 3   3 2 1
1 3 3   3 3 1
1 1 3   1 3 1
2 1 3   2 3 1
3 1 3   3 3 1
1 3 1
3 1 1
1 3 2   3 1 2
1 3 3
3 1 3

可以观察到，重复现象只会出现在边界。就比如第一种113的来源是先固定xz，让其盛放最小值1和最大值3，然后中间的2是自由变量y所决定的。但是第二种113就来源于yz固定x自由。所以这样就会出现一种重复的情况。对于ei和hi变化，他们重复的次数都是6次，就是三个位置中任选两个位置来放最大值和最小值的C(3,2)，再乘以那个重复数字的来源是来自于固定还是自由，所以再乘以2，一共就是3*2=6种重复。

所以总共的情况一共 6*（hi-ei+1)-6=6*（hi-ei)种。
即 6*(h1-e1)*6（h2-e2)……，由于是幂指数相减，考虑L/G就可。如果不能整除，即没有（x,y,z)满足条件。


代码：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=10000000;
bool vis[maxn];
int  prime[maxn/10],factor[maxn],len=0;

void printvis()
{
    for(int i=2;i<maxn;i++)
    {
        if(!vis[i])
        {
            prime[len++]=i;
            for(int j=i+i;j<maxn;j+=i)
            {
                vis[j]=1;
            }
        }
    }
}

void getzhishu(int nn)
{
    int cas=0;
    for(int i=0;i<len&&prime[i]*prime[i]<=nn;i++)
    {
            while(nn%prime[i]==0)
            {
                factor[cas]++;
                nn/=prime[i];
            } 
          if(factor[cas]!=0)cas++;
    }
    if(nn>1)  factor[cas]=1;
}

int main()
{
     printvis();
     int t;
     cin>>t;
     while(t--)
     {
        memset(factor,0,sizeof(factor));
         int g,l;
        int sum=1;
        cin>>g>>l; 
        if(l%g!=0)
        {
            cout<<"0"<<endl;
            continue;
         }
         int k=l/g;
         getzhishu(k);
         for(int i=0;;i++)
         {
            if(factor[i]==0)
            break;
            sum*=factor[i];
            sum*=6;
         }
         cout<<sum<<endl; 
      }
      return 0;
}