hdu 5019 Revenge of GCD

本文主要是介绍hdu 5019 Revenge of GCD，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

        题意：两个数x，y，求他们第k大的公约数。

        思路：先用欧几里德算法求出最大公约数z，然后求z的所有约数，排序，取第k大的。因为z的约数是x，y的公约数的充要条件。

#include <iostream>             
#include <stdio.h>             
#include <cmath>             
#include <algorithm>             
#include <iomanip>             
#include <cstdlib>             
#include <string>             
#include <string.h>             
#include <vector>             
#include <queue>             
#include <stack>             
#include <map>           
#include <assert.h>  
#include <set>           
#include <ctype.h>                  
#define ll long long         
#define max3(a,b,c) max(a,max(b,c))using namespace std;   ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);
}int main(){int n;cin>>n;while(n--){ll x,y,k;cin>>x>>y>>k;ll z=gcd(x,y);set<ll> fac;ll end=sqrt(z+1.0);for(ll i=1;i<=end;i++){if(z%i)continue;fac.insert(i);fac.insert(z/i);}ll cnt=fac.size();if(k>cnt){cout<<"-1"<<endl;}else{int time=0;for(set<ll>::iterator it=fac.begin();it!=fac.end();it++){if(time==cnt-k){cout<<*it<<endl;break;}time++;}}}return 0;
}

这篇关于hdu 5019 Revenge of GCD的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---