hdu 5018 Revenge of GCD-白红宇

hdu 5018 Revenge of GCD

阅读量：4954 次

发布时间：2019-06-12

本文共 1235 字，大约阅读时间需要 4 分钟。

题意：

给你两个数：X和Y 。输出它们的第K大公约数。若不存在输出 -1

数据范围：

1 <= X, Y, K <= 1 000 000 000 000

思路：

它俩的公约数一定是gcd(X,Y)的因数。（把它俩分解成质因数相乘的形式就可以看出）

故找出gcd(x,y)所有的因数，从大到小排序，输出第K个即可。

代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             #include 
              
               using namespace std;int const uu[4] = { 1,-1,0,0};int const vv[4] = { 0,0,1,-1};typedef long long ll;int const maxn = 50005;int const inf = 0x3f3f3f3f;ll const INF = 0x7fffffffffffffffll;double eps = 1e-10;double pi = acos(-1.0);#define rep(i,s,n) for(int i=(s);i<=(n);++i)#define rep2(i,s,n) for(int i=(s);i>=(n);--i)#define mem(v,n) memset(v,(n),sizeof(v))#define lson l, m, rt<<1#define rson m+1, r, rt<<1|1ll gcd(ll a,ll b){ return b==0?a:gcd(b,a%b);}ll factor[1000005];ll x,y,k;int T;bool cmp(ll a,ll b){ return a>b;}int main(){ cin >> T; while(T--){ scanf("%I64d%I64d%I64d",&x,&y,&k); ll d = gcd(x,y); ll m = sqrt(d+0.5); int num = 0; rep(i,1,m) if(d%i==0){ factor[++num] = i; if(i!=d/i) factor[++num] = d/i; } sort(factor+1,factor+1+num,cmp); if(k>num) printf("-1\n"); else printf("%I64d\n",factor[k]); }}