题目来源：http://acm.hdu.edu.cn/showproblem.php?pid=4497
GCD and LCM
Time Limit: 2000/1000 MS
(Java/Others) Memory Limit: 65535/65535 K
(Java/Others)
Total Submission(s):
675 Accepted Submission(s):
312
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
Sample Output
分析：
题意：gcd(x,y ,z) = G lcm(x, y , z)= L，
问有多少种这样的组合数（x, y,z），题目要求有序，故为排列问题。
1：
我们可以转换为求gcd(x/G , y/G , z/G)=1 , lcm (x/G, y/G ,z/G) =
L/G; 即求gcd(x,y,z)=1 qie
lcm(x,y,z)=n=L/G，的排列数。
我们对n进行质因子分解为 n =
p1^r1*p2^r2*......*pm^rm
2：由于质因子满足乘法原则 ， 我们对每一个质因子 讨论 pi^ri,
由于gcd(x,y,z)=1 ,可以断定 x,y,z 有个数一定是pi^0次，
由于lcm(x,y,z)=pi^ri*....,我们可以断定 x,y,z 中一定有一个数能被 pi^ri 整除,
那么另一个数 就可以取 0 ，1，...， ri 中的任意一个数。因此，我们将 ri个 pi 放入 x, y,
z 三个数中， 分两种情况：
一种是 ：
0 ri 0/ri ，这种情况的排列一共是 2*3= 6种
另一种是 ：
0 ri 1/2.../ri-1 ，这种情况的排列一共是
（ri-1）*6种
两种情况之和为
：
6*ri 。
代码如下：
#include<iostream>
#include<stdlib.h>
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
#define N 100005
using namespace std;
map<int , int >factor;
map<int ,int >::iterator it;
void prime(int x)
{
int i,num;
for(i=2;i*i<=x ;i++)
{
if(x%i ==0){
num=0;
while(x%i ==0)
{
x/=i;
num++;
}
factor[i]=num;
}
}
if(x>1)
factor[x]=1;
}
int main()
{
int t,g,l,n,sum;
cin>>t;
while(t--)
{
sum=1;
factor.clear();
cin>>g>>l;
if(l%g)
{
puts("0");
continue;
}
n=l/g;
prime(n);
for(it=factor.begin(); it!=factor.end() ; it++)
sum*=(6*it->second);
cout<<sum<<endl;
}
return 0;
}
hdu 4497 数论 质因子,布布扣,bubuko.com
hdu 4497 数论 质因子
原文：http://www.cnblogs.com/zn505119020/p/3600840.html
