本文主要是介绍hdu 4497 GCD and LCM(组合数学),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目链接:hdu 4497 GCD and LCM
题目大意:给出三个数的最大公约数和最小公倍数,问说有多少种三个数满足。
解题思路:首先用k=l/g,剩下的数即为三个中还需要存在的因子的乘积。然后将k分解成质因子;
以6 72为例,k = 72/6=12,k分解成质因子为2,2,3,不同因子间肯定是互相不影响的,只要计算出每种因子的放法,相乘即为总数。
现在考虑2这个因子,总共有两个c=2.首先可以确定的是三个数中肯定有一个数包含因子为2^c,所以C(3,1)选中一个为该数;
然后剩下两个位置,一个位置肯定不能含有该因子,否则会影响最大公约数的值,所以C(2,1)选中一个位置不能有该因子;
那么最后剩下的一个位置就有1~c-1和0两种可能;并且0是比较特殊的,只会有一种而不是两种,如果这里不单独考虑,则在C(2,1)那步将重复计算两个位置均为空的情况。
然后还有一个比较特殊的就是存在两个位置为2^c,单独考虑C(3,2);
最后公示化简为6*c。
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>using namespace std;typedef long long ll;
ll g, l;ll solve () {if (l%g)return 0;ll ans = 1;ll k = l / g;ll t = sqrt((double)k);for (ll i = 2; i <= t; i++) {if (k % i)continue;ll c = 0;while (k%i == 0) {c++;k /= i;}ans = ans * 6 * c;}if (k != 1)ans = ans * 6;return ans;
}int main () {int cas;scanf("%d", &cas);while (cas--) {cin >> g >> l;cout << solve() << endl;}return 0;
}
这篇关于hdu 4497 GCD and LCM(组合数学)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!