HDU44979 GCD and LCM (素因子分解+计数)
来源：程序员人生 发布时间：2014-11-25 07:58:32 阅读次数：2401次
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4497
题意：
求有多少种(x,y,z)使得最小公倍数为l，最大公约数为g
分析：
我们将l,g进行素因子分解；
很明显当g有l没有的素因子 和g的某1个因子的次数大于l的这个因子的次数的时候答案为0；
然后是有答案的情况下，我们设g中某1个因子数的次数为num1,l中这个因子的次数为num2;
那末在决定x,y,z在这个因子上的次数时我们要这样斟酌，最少有1个为num1,最少有1个为
num2,然后根据容斥原理可以得出这类情况的方案数
代码许下：
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <map>
using namespace std;
int G[2][50],L[2][50];
int gcd(int a,int b)
{
if(b) return gcd(b,a%b);
return a;
}
int main()
{
int t,g,l;
scanf("%d",&t);
while(t--){
scanf("%d%d",&g,&l);
int cnt1=0,cnt2=0;
memset(G,0,sizeof(G));
memset(L,0,sizeof(L));
map<int ,int >mp1;
map<int ,int >mp2;
for(int i=2;i<=g;i++){
if(g%i==0){
G[0][cnt1]=i;
while(g%i==0){
G[1][cnt1]++;
g/=i;
}
cnt1++;
}
}
if(g>1){G[0][cnt1]=g;G[1][cnt1++]=1;}
for(int i=2;i<=l;i++){
if(l%i==0){
L[0][cnt2]=i;
while(l%i==0){
L[1][cnt2]++;
l/=i;
}
cnt2++;
}
}
if(l>1) {L[0][cnt2]=l;L[1][cnt2++]++;}
bool flag=0;
for(int i=0;i<cnt1;i++)
mp1[G[0][i]]=G[1][i];
for(int i=0;i<cnt2;i++)
mp2[L[0][i]]=L[1][i];
for(int i=0;i<cnt1;i++){
if(mp1[G[0][i]]>mp2[G[0][i]])
flag=1;
}
if(flag){ puts("0"); continue;}
long long ans=1;
//cout<<cnt1<<" "<<cnt2<<endl;
/*****
cout<<"*******"<<endl;
for(int i=0;i<cnt1;i++)
cout<<G[0][i]<<" "<<G[1][i]<<endl;
cout<<"*******"<<endl;
for(int i=0;i<cnt2;i++)
cout<<L[0][i]<<" "<<L[1][i]<<endl;
cout<<"*******"<<endl;
******/
for(int i=0;i<cnt2;i++){
int num1=mp1[L[0][i]];
int num2=mp2[L[0][i]];
if(num1==num2) continue;
long long tmp = (num2-num1+1)*(num2-num1+1)*(num2-num1+1);
tmp-=2*(num2-num1)*(num2-num1)*(num2-num1);
tmp+=(num2-num1⑴)*(num2-num1⑴)*(num2-num1⑴);
ans*=tmp;
cout<<"tmp "<<tmp<<endl;
}
cout<<ans<<endl;
}
return 0;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
