题目链接: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 1695 GCD(欧拉函数+容斥原理).docx
For example, the LCM of 5, 7 and 15 is 105. Input Input will consist of multiple problem instances. The first line of the input will contain a single integer indicating the number of problem ...
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu 1166线段树代码
HDU最全ac代码
hdu动态规划算法集锦
自己做的HDU ACM已经AC的题目
hdu题目分类
HDU图论题目分类