程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu5019Revenge of GCD（枚舉+gcd）

hdu5019Revenge of GCD（枚舉+gcd）

編輯：C++入門知識

hdu5019Revenge of GCD（枚舉+gcd）

題目鏈接：

huangjing

題意：
求出兩個數的第k大的GCD
思路：
首先求出最大公約數，我最開始的思路是打一個很大的素數表，然後不斷的進行除，求出第k大的，但是一直re，後來知道可以直接把最大公約數的約數全部求出來，排序即可。。然後因為約數不確定，所以stl裡的vector是個不錯的選擇。

思路：

Revenge of GCD

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 933 Accepted Submission(s): 282

Problem Description In mathematics, the greatest common divisor (gcd), also known as the greatest common factor (gcf), highest common factor (hcf), or greatest common measure (gcm), of two or more integers (when at least one of them is not zero), is the largest positive integer that divides the numbers without a remainder.
---Wikipedia

Today, GCD takes revenge on you. You have to figure out the k-th GCD of X and Y.
Input The first line contains a single integer T, indicating the number of test cases.

Each test case only contains three integers X, Y and K.

[Technical Specification]
1. 1 <= T <= 100
2. 1 <= X, Y, K <= 1 000 000 000 000

Output For each test case, output the k-th GCD of X and Y. If no such integer exists, output -1.
Sample Input

Sample Output

1
-1
2

Source BestCoder Round #10
Recommend heyang | We have carefully selected several similar problems for you: 5041 5040 5039 5037 5036
代碼：

#include
#include
#include
#include
#include
#include
#include
#include
#include
#define eps 1e-9
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;

ll xx,yy,kk;

ll gcd(ll a,ll b)
{
    if(b==0)  return a;
    else  return gcd(b,a%b);
}

vectorvec;

int main()
{
     ll i;
     int t;
     scanf("%d",&t);
     while(t--)
     {
        scanf("%I64d%I64d%I64d",&xx,&yy,&kk);
        ll  ans=gcd(xx,yy);
        vec.clear();
        vec.push_back(1);
        if(ans!=1)
            vec.push_back(ans);
        if(i*i==ans)
            vec.push_back(i);
        for(i=2;i*ivec.size())
              printf("-1\n");
        else
              printf("%I64d\n",vec[vec.size()-kk]);
    }
     return 0;
}