HDU 5019 簡單數學題
來源：程序員人生 發布時間：2014-09-29 16:05:09 閱讀次數：3034次
這道題是說給定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;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
