HDU 4497 GCD and LCM （分解质因数）

题意：

给你G，L，问你以G为最大公约数且以L为最小公倍数的三元组（x，y，z）有多少种，注意：（1，2，3）和（1，3，2）是不同的。

思路：

我们要找满足 gcd(a,b,c)=G,lcm(a,b,c)=L 的 a，b，c，所以如果存在的话，那么必有 a=0(modG) ，bc同理。同时： L=0(moda) ，bc同理。 所以，直接判断L%G是否为零，如果不为零，则不可能出现这种情况。 下面讨论为零的情况： 将a，b，c，G，L分解质因数 ( pi 代表分解出来的素数 ai 代表次数(可以为0)，下同)：

a=pa11∗pa22∗pa33∗pa44...... b=pb11∗pb22∗pb33∗pb44...... c=pc11∗pc22∗pc33∗pc44...... G=pG11∗pG22∗pG33∗pG44...... L=pL11∗pL22∗pL33∗pL44......

由此可见，对于G来说：

Gi=min(ai,bi,ci) 对于L来说： Li=max(ai,bi,ci)

我们只要把所有的 (ai,bi,ci) 确定了，那么a，b，c就确定了，也就找到了一组解。 又因为上边的那两个式子，所以 (ai,bi,ci) 必满足最大的等于 Li 最小的等于 Gi ，另外的则取这两个值之间的任意一个值，即 [GiLi] ，也就可以转化一下：直接对L/G = k进行质因数分解，那么第三个数的取值范围就成了 [0,ki] ，然后计数即可。

举个例子：

6，72 k=72/6=12 k=22∗31 所以对于2这个素数来说，可知满足条件的前两个数为0，2 (为保证三个数gcd和lcm的规则，所以前两个数分别为gcd和lcm)，第三个数在[0,2]，当第三个数取0时，002这三个数可以有三种排列，当第三个数取2时，022可以有三种排列，当第三个数取1时，012有6种排列。 所以 3 + 3 + 6 = 12种。 然后对于素数3，可知满足条件的前两个数为0，1，第三个数在[0,1]，所以同理 3+3 = 6种排列。 所以最终答案是 12 * 6 = 72 种。 上边的对于素数的操作用公式表示即为： 3+3+(ki−1)∗6 即为：

6∗ki 最后把所有的乘起来就是答案了。

AC代码：

#include <iostream> #include <cstdio> using namespace std; int main() { int t; cin>>t; int g,l; long long int ans; int m; while(t--){ scanf("%d%d",&g,&l); if(l%g != 0){ printf("0\n"); } else{ int k = l/g; ans = 1; m = 0; for(int i = 2;i <= k;i++){ while(k % i == 0){ m++; k /= i; } if(m != 0) ans *= ( 6*m ); m = 0; } printf("%I64d\n",ans); } } return 0; }