首页 > 代码库 > ABK
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≤109 , 1≤K≤10) 输出每行输出一个整数d,表示A,B的第K大公约数 若没有第K大的公约数则输出-1。 样例输入712 24 112 24 212 24 312 24 412 24 512 24 612 24 7 样例输出1264321-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 else18 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 }
ABK
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。