ABK （枚举）

ABK
Accepted : 24		Submit : 176
Time Limit : 1000 MS		Memory Limit : 65536 KB

题目描述

ABK是一个比A+B还要简单的题目,给出两个整数A,B,求出A和B的第K大公约数。

输入

第一行是一个整数N（N ≤ 10000），表示样例的个数。以后每行一个样例，为3个整数A，B，K (1≤A,B≤10⁹ , 1≤K≤10)

输出

每行输出一个整数d,表示A,B的第K大公约数若没有第K大的公约数则输出-1。

样例输入

样例输出

ACKNOWLEDGE　　　　http://94it.net/a/jingxuanboke/2015/0112/446859.html

乍一看很简单，可是老是TML(哈哈，结果做的睡着了)，看了人家的思路的确要比自己的耀眼很多。

用了正反枚举.

 1  #include<iostream>
 2  #include<cstdio>
 3  #include<cstring>
 4  #include<string>
 5  #include<map>
 6  #include<algorithm>
 7  #include<set>
 8  #include<cmath>
 9  #include<vector>
10 using namespace std;
11 
12 int a,b,k;
13 int gcd(int a,int b)
14 {
15     if(b==0)
16         return a;
17     else
18         return gcd(b,a%b);
19 
20 }
21 void solve()
22 {
23     int mx=gcd(a,b),cnt=0;
24     for(int i=1;i*i<=mx;i++) //正向枚举
25         if(mx%i==0)
26         {
27             cnt++;
28             if(cnt==k)
29             {
30                  cout<<mx/i<<endl;
31                  return;
32             }
33         }
34 
35     for(int i=floor(sqrt(mx)+0.5);i>=1;i--) //反向枚举//用floor为了避免误差
36         if(mx%i==0)
37         {
38             cnt++;
39 
40             if(i*i==mx)
41                 cnt--; //小细节，如果gcd的算数平方根正好是整数，反向枚举的第一个i和正向枚举的最后一个i重复了
42             if(cnt==k)
43             {
44                 cout<<i<<endl;
45                 return;
46             }
47         }
48     if(cnt<k)
49         cout<<"-1"<<endl;
50  }
51 
52  int main()
53  {
54     // freopen("a.txt","r",stdin);
55  int T;
56  cin>>T;
57  while(T--)
58  { cin>>a>>b>>k; solve(); }
59  return 0;
60  }

正反枚举