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 
#include 
#include 
#include 
#include 
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;
}