题意：
求出两个数的第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); } vector
           
            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
            
             vec.size()) printf("-1\n"); else printf("%I64d\n",vec[vec.size()-kk]); } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：poj 1753 Flip Game （bfs + 枚举..	下一篇：HDU 4862 Jump （最小K路径覆盖）

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: