首页 > 代码库 > hdu5019Revenge of GCD（枚举+gcd）

hdu5019Revenge of GCD（枚举+gcd）

2024-07-23 21:31:56   219人阅读

题目链接：

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
3
2 3 1
2 3 2
8 16 3
 

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<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<vector>
#include<cmath>
#include<string>
#include<queue>
#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);
}

vector<ll>vec;

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*i<ans;i++)
          {
              if(ans%i==0)
              {
                  vec.push_back(i);
                  vec.push_back((ll)ans/i);
              }
          }
        sort(vec.begin(),vec.end());
       // printf("%d\n",vec.size());
        if(kk>vec.size())
              printf("-1\n");
        else
              printf("%I64d\n",vec[vec.size()-kk]);
    }
     return 0;
}


hdu5019Revenge of GCD（枚举+gcd）


联系
我们