本文主要是介绍hdu 4497 GCD and LCM（排列组合），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：hdu 4497 GCD and LCM
题目大意：给出三个数的最大公约数，和最小公倍数，问这三个数的排列组合关系。
解题思路：最小公倍数/最大公约数 == 三个数不同部分的乘积。这样来考虑的话，三个数都要有最大公约数的部分，其余的部分就是由LCM / GCD 里面的因子构成。这里面的因子可能会有 2 2 3 这样的情况， 不同的因子之间是不会相互干扰的，但是相同的会出现问题，因为，不能同时将相同的因子都放在三个位置上，这样最大公约数就的要乘上这个因子。然后对于单种因子来考虑的话，每种因子只能放在两个位置上这样就有 3 种选择，然后如果这类因子里有多个的话，一个放全部即n个这个因子，但是第二个可以放 0 。。 n个，分情况的话 1 。。 n - 1 的情况， 就有 3 * 2 （哪一堆拿来放满的） * （n - 1）， 两个为空的那一种 3 * 1 ， 还有一种是两个都是n个， 种类就是3 * 1 ，这样化简后就是6 * n。
推出这个后就只要把LCM / GCM 这个数拿来因式分解，得到每个不同的因子，代入公式计算就可意得到结果。
代码：
#include <stdio.h>
#include <math.h>int t;int main () {scanf ("%d", &t);int g, l, k, count, ans;while (t--) {scanf ("%d%d", &g, &l);ans = 1;if (l % g != 0)printf ("0\n");else {l /= g;k = sqrt(l); for (int i = 2; i <= k; i++) {count = 0;if (l % i == 0) {while (l % i == 0) {l /= i;count++;}}if (count)ans *= 6 * count;}if (l != 1)ans *= 6;printf ("%d\n", ans);}}
}
这篇关于hdu 4497 GCD and LCM（排列组合）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
