之前在学习中，做过一些数论的题，但是都忘记了，所以从现在开始，数论的题目也纳入我的博客之中，但是又不太好分类，终于在网上找到了一道例题，巩固了一下基础，HDU4497，接下来分享一些知识还有这道题的题解。

题目大意：给你一个LCM与GCD，问是否存在(x,y,z)这样一组解，使得这三个数的LCM为n，GCD为m，输入n与m，求出(x,y,z)解的总数。

一、两个数的GCD与LCM

三个数的太难理解，我们首先看一下两个数 如果两个数的最大公约数是2，最小公倍数是10，那么这两个数是多少？答案是2与10.还有别的解吗？我们来看看有多少组。

第一步：我们思考，既然m是x,y的最大公约数，所以x%m==0&&y%m==0，然后想一下，LCM%GCD是否为0？

我们来看一下LCM与GCD的定义。假设 x，y的最大公约数是 GCD，最小公倍数是LCM，根据唯一分解定理：

x=p1^a1*p2^a2*p3^a3*......pn^an

y=p1^b1*p2^b2*p3^b3.......pn^bn

这里注意x的p1与y的p1可能不相同。

LCM是x与y共同出现过质因子的最大值LCM=p1^max(a1,b1)*p2^max(a2,b2)......pn^max(an,bn)

GCD是x与y共同出现过的质因子的最小值GCD=p1^min(a1,b1)*p2^min(a2,b2)......pn^min(an,bn) PS：没有出现过也可以理解为出现过，最小幂是0。取幂是取0就好。

因为他们都有共同出现过的因子，所以LCM一定可以整除以GCD。

第二步：既然都可以整除以GCD，那么我们就令，x/m,m/m,y/m,n/m，这个时候问题就变成了x/m与y/m的最大公约数是1，最小公倍数是n/m。

第三步：n/m有x/m和y/m所有的质因子，所以我们把n/m分解，对于n/m的每一个质因子 例如质因子 p出现的次数出现了x1次，那么根据最小公倍数的定义，x/m与y/m的p质因子的幂，其中一个要为x1。又因为他们两个的最大公约数为1，所以另一个数质因子p的幂必须为0。所以这里有两种组合,每一个质因子都有两种。所以答案是2^h组，h为LCM/GCD的因子的个数。

第四步：举例验证，例如上题中，GCD为2，LCM是10,10/2=5,5的因子个数只有一种，所以GCD为2，LCM为10的(x,y)只有两组，就是2 10与10 2。如果不交换重复那么就是 2^(h-1),h为LCM/GCD的因子的个数。

 

二、三个数的GCD与LCM

现在言归正传，做一下HDU4497这道题，根据上述我们的推论，一步一步来。

首先如果LCM不能整除以GCD那么一定是0组解，也就是不需要算了。(证明在上面已经证明过了).

如果可以整除以GCD，我们按照两个数的步骤来，假设五个数为 a,b,c,l(LCM),g(GCD)。

 第一步：a/g,b/g,c/g,l/g,g/g。

第二步：与两个数的论述相同，将l/g质因子分解，假设它的一个质因子p的幂是x1，那么a/g,b/g,c/g的质因子p的幂其中一个为x1，又由于三者的最大公约数为1，则三者中质因子p的幂，还应该有一个为0，那么我们假设a为0，b为x1，那么c有【0，x1】种选择，同样如果b为x1，a为0，那么c也有【0，x1】种，c有三种选择，所以一共有6x1种(即A(3,2))。

第三步：将每种质因子的可能撑起来，即6x1*6x2*6x3，然后输出结果。不能重复的话没有证明，要么除2要么除3，根据样例试吧hiahiahia。

第四步：写一下程序，注释加AC代码：

#include <queue>
#include <cstdio>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <iostream>
#include <stack>
#include <sstream>
#include <vector>
#define MIN(x,y) ((x)<(y)?(x) : (y))
#define MAX(x,y) ((x)>(y)?(x) : (y))
using namespace std;
typedef long long ll;
const int maxn=1e6+5;
const ll INF=1e9;
/*中国有句古话，叫作置之死地而后生*/
/*Wrod in CHina,killing make you Stronger*/
ll cnt=0;
bool vis[maxn];
int prime[maxn];
int main()
{
    memset(vis,1,sizeof(vis));//欧拉筛素数打表。
    for(int i=2;i<maxn;i++)
    {
        if(vis[i]) prime[++cnt]=i;
        for(int k=1;k<=cnt&&i*prime[k]<maxn;k++)
        {
            vis[i*prime[k]]=0;
            if(i%prime[k]==0) break;
        }
    }
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int g,l;
        ll ans=1;
        ll ans1=0;
        int flag=0;
        scanf("%d%d",&g,&l);
        if(l%g) puts("0");
        else
        {
            ll k=l/g;
            for(int i=1;i<=cnt&&prime[i]*prime[i]<=k;i++)
            {
                ans1=0;flag=0;
                while(k%prime[i]==0)
                {
                    flag=1;
                    ans1++;
                    k/=prime[i];
                }
                if(flag)
                ans*=6*ans1;//满足6x1种可能，然后根据计数原理相乘。
            }
            if(k>1) ans*=6;//如果k>1，表示k一定是素数，且幂次为1
            printf("%lld\n",ans);
        }
    }
    return 0;
}