首页 > ACM题库 > HDU-杭电 > HDU 4497-GCD and LCM -数论-[解题报告]HOJ
2015
07-17

HDU 4497-GCD and LCM -数论-[解题报告]HOJ

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

题意:已知l,g其中g=gcd(x,y,z),l=lcm(x,y,z),问有x,y,z多少种组合使得关系成立。
        题解:已知x%g=y%g=z%g=0,l%x=l%y=l%z=0,所以l%g=0。这个可以判定是否存在(x,y,z)符合条件。

又l/g=p1^a1*p2^a2*p3^a3*…pk^ak.(pi为素数)

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

所以min(bi,ci,di)=0,不然最大公约数是pi^min(ai,bi,ci)*g>g,同理得到max(bi,ci,di)=ai。

之后就是怎么安排(bi,ci,di),其中一个为0,一个为ai,另一个任意0<=k<=ai。使用容斥原理求:

对pi指数的所有可能方案数:fi=所有的方式(ai+1)^3-不含0的情况ai^3-不含ai的情况ai^3+重复删去的即不含0,也不含ai的情况(ai-1)^3

所以答案就是ans=∑fi(1<=i<=k,fi=(ai+1)^3-2*ai^3+(ai-1)^3)

耗时:15MS

#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;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/a601025382s/article/details/12109307