Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Others)Total Submission(s): 50 Accepted Submission(s): 27
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吉林通化全国邀请赛——题目重现 1 1 1 A32=6 #include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <cstdlib> #include <algorithm> #include <vector> #include <stack> #include <queue> #include <set> #include <sstream> #include <map> #include <bitset> using namespace std ; #define zero {0} #define INF 2000000000 #define eps 1e-6 typedef long long LL; #define MAX 100000 int prime[MAX]=zero; int Prime(int a[],int n) { int i,j,k,x,num,*b; n++; n/=2; b=(int *)malloc(sizeof(int)*(n+1)*2); a[0]=2;a[1]=3;num=2; for(i=1;i<=2*n;i++) b[i]=0; for(i=3;i<=n;i+=3) for(j=0;j<2;j++) { x=2*(i+j)-1; while(b[x]==0) { a[num++]=x; for(k=x;k<=2*n;k+=x) b[k]=1; } } return num; } int main() { #ifdef DeBUGs freopen("C:\\Users\\Sky\\Desktop\\1.in","r",stdin); #endif int maxn; maxn=Prime(prime,MAX); int i,j,k; int T; scanf("%d",&T); while(T--) { int gcd,lcm; scanf("%d%d",&gcd,&lcm); if(gcd==0||lcm==0) { printf("0\n"); continue; } if(lcm%gcd) { printf("0\n"); continue; } int de=lcm/gcd; int num=0; int sum=1; for(i=0;prime[i]<=de&&i<maxn&&prime[i]>0;i++) { num=0; while(de%prime[i]==0) { de/=prime[i]; num++; } if(!num) continue; sum*=num*6; } if(de>1) sum*=6; printf("%d\n",sum); } return 0; } View Code
转载于:https://www.cnblogs.com/Skyxj/p/3279704.html
相关资源：数据结构—成绩单生成器