HDU44979 GCD and LCM (素因子分解+計數)
來源：程序員人生 發布時間：2014-11-25 07:58:32 閱讀次數：2582次
題目鏈接：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;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
