hdu-4497-GCD and LCM-gcd的性质

lcm(x,y,z)=k;

gcd(x,y,z)=t;

若：x=a*t;   y=b*t;       z=c*t;

则lcm(a,b,c)=k/t;

若k/t=2^A;

则a,b,c中至少有一个数为2^A,至少有一个数是2^0,另外一个数为2^(0~A);共6*A种情况。

则，若k/t=2^A*3^B*5^C;

a,b,c的情况数为：(6*A)*(6*B)*(6*C);

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
#define INF ((1<<31)-1)//2147483647
#define INFF ((1<<30)-1)//1073741823
#define MOD 1000000007
#define LL __int64
const int N = 100000;
bool a[N];
int p[N];
int num;
void Prime() {
    memset(a, 0, sizeof(a));
    int  i, j;
    for(i = 2; i < N; ++i) {
        if(!(a[i])) p[num++] = i;
        for(j = 0; (j<num && i*p[j]<N); ++j) {
            a[i*p[j]] = 1;
            if(!(i%p[j])) break;
        }
    }
}
int main()
{
    int T,g,l,t,i;
    num=0;
    Prime();
    LL ans=0;
    while(~scanf("%d",&T))
    {
        while(T--)
        {
            ans=1;
            scanf("%d%d",&g,&l);
            if(l%g)
            {
                cout<<"0"<<endl;
                continue;
            }
            t=l/g;
            for(i=0;i<num;i++)
            {
                if(p[i]>t)break;
                LL a=0;
                while(t%p[i]==0)
                {
                    a++;
                    t=t/p[i];
                }
                if(a)
                {
                    ans=ans*(6*a);
                }
            }
            if(t>1)ans=ans*6;
            cout<<ans<<endl;
        }
    }
    return 0;
}

hdu-4497-GCD and LCM-gcd的性质,布布扣,bubuko.com

hdu-4497-GCD and LCM-gcd的性质

原文：http://blog.csdn.net/rowanhaoa/article/details/21748293