首页 > 代码库 > 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