GCD and LCM HDU - 4497

http://acm.hdu.edu.cn/showproblem.php?pid=4497

将gcd與lcm素因子分解 如果gcd某個素因子的幂次pi大于lcm對應素因子的幂次qi 那就是湊不出 因為gcd肯定是lcm因子

如果pi<=qi xyz三個數中必有一個幂次為pi 必有一個為qi 因為gcd就是取得三者最小 lcm取最大 隻剩一個數的幂次ti可變 當ti=pi或ti=qi時 可以産生3!/2!種可能 意思是把這三個幂次全排列一下 當ti!=pi且ti!=qi時 則産生3!種可能 幂次内加法原理 幂次之間乘法原理即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e2+10;

int main()
{
    ll a1[maxn],a2[maxn],p1[maxn],p2[maxn];
    ll gcd,lcm,ans;
    int t,n1,n2,i,j,flag;
    scanf("%d",&t);
    while(t--){
        scanf("%lld%lld",&gcd,&lcm);

        n1=0;
        for(i=2;i*i<=gcd;i++){
            if(gcd%i==0){
                n1++;
                a1[n1]=i,p1[n1]=0;
                while(gcd%i==0){
                    gcd/=i;
                    p1[n1]++;
                }
            }
        }
        if(gcd!=1){
            n1++;
            a1[n1]=gcd,p1[n1]=1;
        }

        n2=0;
        for(i=2;i*i<=lcm;i++){
            if(lcm%i==0){
                n2++;
                a2[n2]=i,p2[n2]=0;
                while(lcm%i==0){
                    lcm/=i;
                    p2[n2]++;
                }
            }
        }
        if(lcm!=1){
            n2++;
            a2[n2]=lcm,p2[n2]=1;
        }
        /*
        printf("***%d***\n",n1);
        for(i=1;i<=n1;i++){
            printf("%lld %lld\n",a1[i],p1[i]);
        }
        printf("***%d***\n",n2);
        for(i=1;i<=n2;i++){
            printf("%lld %lld\n",a2[i],p2[i]);
        }
        */
        i=1,j=1,flag=1,ans=1;
        while(i<=n1&&j<=n2){
            if(a1[i]<a2[j]){
                flag=0;
                break;
            }
            else if(a1[i]==a2[j]){
                if(p1[i]>p2[j]){
                    flag=0;
                    break;
                }
                else if(p1[i]<p2[j]){
                    ans*=6*(p2[j]-p1[i]);
                }
                i++,j++;
            }
            else{
                ans*=6*p2[j];
                j++;
            }
        }
        if(i<=n1) flag=0;
        while(j<=n2){
            ans*=6*p2[j];
            j++;
        }
        if(flag) printf("%lld\n",ans);
        else printf("0\n");
    }
    return 0;
}