GCD and LCM
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Others)
Total Submission(s): 3409 Accepted Submission(s):
1503
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 翻译:给出g和l,求满足gcd(x,y,z)=g,lcm(x,y,z)=l的(x,y,z)组合的数量,(1, 2, 3)和(1, 3, 2)算作不同组合 分析: g是因数,l是倍数,显然可以得到x%g=y%g=z%g=0=l%x=l%y=l%z; 进一步推出l%g=0;若不符合,无解。 根据唯一分解定理 将x,y,z分解 x=p1^a1*p2^a2……ps^as;
y=p1^b1*p2^b2……ps^bs;
z=p1^c2*p2^c2……ps^cs; g是三个数的最大公约数,则g满足g=p1^min(a1,b1,c1)……ps^min(as,bs,cs)=p1^e1……ps^es l是三个数的最小公倍数,则l满足l=p1^max(a1,b1,c1)……ps^max(as,bs,cs)=p1^h1……ps^hs ei=min(ai,bi,ci) hi=max(ai,bi,bi) x,y,z三个数分解后,对于每一个质因子,必然有一个指数是ei,一个指数是hi,先将这两个数固定下来 另一个数可以取ei到hi之间的数,包括ei和hi,设为ti (1)当ti=ei或者ti=hi时,(ei,ei,hi)只有三种组合方式,(ei,hi,hi)也只有三种组合方式 (2)当ti≠ei并且ti≠hi时,(ei,ti,hi)有6种组合方式 (3)当ei=ti=hi时,只有1种组合方式 当ei≠hi时,则每个质因子全部的组合方式有6*(hi-ei)种,组合数用乘法计算结果,当hi=ei,不累乘0
#include<stdio.h> #include<math.h> #include<string.h> #include<algorithm> #include<string> #include<vector> #include<iostream> #include<cstring> #define inf 0x3f3f3f3f using namespace std; #define ll long long const int maxx=1e6+5; int prime[maxx]; int vis[maxx]; ll g,l; int cnt; void init() { memset(vis,true,sizeof(vis)); vis[0]=vis[1]=false; cnt=0; for(int i=2;i<=maxx;i++) { if(vis[i]) prime[cnt++]=i; for(int j=0;j<cnt && prime[j]*i<=maxx;i++) { vis[ i*prime[j] ]=false; if(i%prime[j]==0) break; } } } int main()///hdu4497 { init(); int t; scanf("%d",&t); while(t--) { ll ans=1; scanf("%lld%lld",&g,&l); if(l%g) printf("0\n"); else { for(int i=0;i<cnt;i++) { int e=0,h=0; while(g%prime[i]==0) { e++; g=g/prime[i]; } while(l%prime[i]==0) { h++; l=l/prime[i]; } if(h-e) { ans=ans*(h-e)*6; } } if(g==l)///32位范围内大素数因子只能有一个,l能被g整除证明这个大素数相同,不累乘 ; else if(l>1)///如果g=1,l=大素数,再乘一次6 ans=ans*6; printf("%lld\n",ans); } } return 0; }