HDU 5019 简单数学题
来源：程序员人生 发布时间：2014-09-29 16:05:09 阅读次数：2911次
这道题是说给定A和B，求第C大的公约数。
我们最长求的就是最大公约数了，也就是通常用的GCD算法。但是现在要求第C大的公约数，我们可以想见如果令第C大的公约数为x，最大公约数为g的话，那么x|g的，为什么呢？
我们可以直观的理解，最大公约数其实就是A和B分别进行素因子分解之后，能取到公共素因子乘起来得到的。而对于任意A、B的公约数，那么肯定包含了部分的最大公约数所包含的素因子，因此x|g。
于是要求第C大的公约数，只需要枚举g的因子就行了，我们知道求一个数的因子情况，是可以进行O(sqrt(n))的枚举的，这道题n的范围就是10^12，所以复杂度内是够的。
但是好久没有写这种卡时限很紧的题了，稍微把判断写多了或者多枚举了一些内容就tle了，确实很无力。还是自己太渣。
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <cstdlib>
using namespace std;
typedef __int64 LL;
LL gcd(LL a, LL b)
{
if(b==0)
return a;
return gcd(b, a%b);
}
int main()
{
LL a, b, c;
int T;
vector<LL> v;
scanf("%d", &T);
while(T--)
{
scanf("%I64d%I64d%I64d", &a, &b, &c);
LL temp = gcd(a, b);
v.clear();
int cnt = 0;
for(LL i=1; i*i<=temp; ++i)
{
if(temp%i==0)
{
v.push_back(i);
if(i*i!=temp)
v.push_back(temp/i);
}
}
sort(v.begin(), v.end());
if(v.size() >= c)
printf("%I64d
", v[v.size()-c]);
else
printf("-1
");
}
return 0;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
