HDU - 4497 GCD and LCM

题意：给出三个数的gcd,lcm，求这三个数的所有的可能

思路 ：设x,y,z的gcd为d，那么设x=d*a，y=d*b，z=d*c，a，b，c肯定是互质的，那么lcm=d*a*b*c,所以我们可以得到a*b*c=lcm/gcd=ans,将ans分解因数后，那么每次都要分配每个因数的个数，假设某个因数的个数为n,一定要有两个分配到n，0，所以是6种

#include <iostream>
#include <cstdio>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;

int n,m;
int num[1000000];

int main(){
	int t;
	scanf("%d",&t);
	while (t--){
		scanf("%d%d",&n, &m);
		if (m%n != 0){
			printf("0\n");
			continue;
		}
		m /= n;
		int cnt = sqrt(m+0.5);
		int k = 0;
		for (int i = 2; i <= cnt && m > 1; i++){
			if (m % i == 0){
				num[k] = 0;
				while (m%i == 0){
					++num[k];
					m /= i;
				}
				++k;
			}
		}
		if (m != 1)
			num[k++] = 1;
		int ans = 1;
		for (int i = 0; i < k; i++)
			ans = ans*num[i]*6;
		cout << ans << endl;
	}
	return 0;
}

HDU - 4497 GCD and LCM,布布扣,bubuko.com

HDU - 4497 GCD and LCM

原文：http://blog.csdn.net/u011345136/article/details/24493693