HDU 5019 简单数学题

这道题是说给定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 
#include 
#include 
#include 
#include 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 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\n", v[v.size()-c]);elseprintf("-1\n");}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！