首页 > 代码库 > hdu 5019 Revenge of GCD
hdu 5019 Revenge of GCD
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5019
题目大意:给出A,B两个数,求第k大的公约数,如果没有输出-1
思路:直接把A,B的公约数全部求出来,然后找出来就行啦,当时没有注意数据大小居然是10^12,用的int ,所以果断错啦,赛完才发现,坑呀。。。。。
注意要用long long或是__int64。。。。。
code:
#include<cstdio> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> using namespace std; typedef __int64 LL; LL gcd(LL a,LL b) { LL r; while(b>0) { r=a%b; a=b; b=r; } return a; } bool cmp(LL a,LL b) { return a>b; } LL f[100000]; int main() { int T; LL x,y,k,i,len; scanf("%d",&T); while(T--) { len=0; scanf("%I64d%I64d%I64d",&x,&y,&k); LL r=gcd(x,y); LL d=sqrt(r); while(d*d<=r) d++; //这个循环和接下来的那个循环可以不要不要,只是曾经写过一个代码是这么写过就这么写的 while(d*d>r) d--; for(i=1;i<=d;i++) { if(r%i==0) { if(i*i==r) { f[len++]=i; } if(i*i<r) { f[len++]=i; f[len++]=r/i; } } } sort(f,f+len,cmp); if(len>=k) { printf("%I64d\n",f[k-1]); } else { printf("-1\n"); } } return 0; }
hdu 5019 Revenge of GCD
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。