首页 > 代码库 > hdu 4497 GCD and LCM(唯一分解+容斥原理)

hdu 4497 GCD and LCM(唯一分解+容斥原理)

2024-07-30 16:54:40   220人阅读

GCD and LCM

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


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吉林通化全国邀请赛——题目重现

题意：
求同时满足gcd(x,y,z)==g&&lcm(x,y,z)==L的(x,y,z)组合数.

题解：
1.很直观的：若l%g！=0||g>l时，答案为0；
2.若果满足l%g==0,用唯一分解定理把个g,l分解，用map保存g,l相同因子个数的差
3.对于x,y,z，其对应的质因子pi应该属于[0,s],s为map[pi],pi的个数,而且x,y,z中必须有一个为0，一个为map[pi]，这是为了保证lcm=L,gcd=g;
     每个pi对应的种数累乘就是答案了。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<set>
#include<queue>
#include<stack>
#include<vector>
#include<map>

#define N 100010
#define Mod 10000007
#define lson l,mid,idx<<1
#define rson mid+1,r,idx<<1|1
#define lc idx<<1
#define rc idx<<1|1
const double EPS = 1e-11;
const double PI = acos(-1.0);
const double E=2.718281828;
typedef long long ll;

const int INF=1000010;

using namespace std;

map<int,int>mp;

void Fenjie(int n,int d)
{
    for(int i=2; i*i<=n; i++)
    {
        if(n%i==0)
        {
            while(n%i==0)
            {
                mp[i]+=d;
                n/=i;
            }
        }
        if(n==1)
            break;
    }
    if(n>1)
        mp[n]+=d;
}

int main()
{
    //freopen("in.txt","r",stdin);
    int n;
    while(cin>>n)
    {
        while(n--)
        {
        	mp.clear();
            int g,l;
            cin>>g>>l;
            if(g>l||l%g)
            {
                printf("0\n");
                continue;
            }
            Fenjie(l,1);
            Fenjie(g,-1);
            ll ans=1;
            map<int,int>::iterator it;
            for(it=mp.begin();it!=mp.end();it++)
		{
			if(it->second)
			{
				int x=it->second;
				//ans*=((x+1)*(x+1)*(x+1)-2*x*x*x+(x-1)*(x-1)*(x-1));//容斥原理
				ans*=6*x;//组合原理，c(3,1)*c(2,1)*(x-1+1)
			}
		}
		cout<<ans<<endl;
        }
    }
    return 0;
}


My code:


hdu 4497 GCD and LCM(唯一分解+容斥原理)


联系
我们