学步园

       求k大GCD。题意：给三个正整数x，y和k，求x和y的第k大公约数。

       我的解题思路：首先根据求最大公约数的原理，k大公约数是最大公约数的因子。那么求k大公约数就转换成为了求最大公约数的第k大因子。可以通过唯一分解定理得到最大公约数的因子个数，然后根据情况判断是否枚举。

       我的解题代码：

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <algorithm>

using namespace std;

typedef long long Long;

Long x, y, k;

Long Gcd(Long a, Long b);

Long Factor(Long x);        //返回因子个数

int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%lld %lld %lld", &x, &y, &k);
        Long gcd = Gcd(x, y);
        Long fn = Factor(gcd);
        if (fn < k) puts("-1");
        else if (k == fn) puts("1");
        else if (k == 1) printf("%lld\n", gcd);
        else if (fn % 2 == 1 && (fn - 1) / 2 == k) printf("%lld\n", (Long)sqrt(gcd + 0.5));
        else
        {
            Long cnt = (Long)sqrt(gcd + 0.5) + 1;
            Long times = 0;
            for (Long i=1; i<cnt; ++i)
            {
                if (gcd % i == 0)
                {
                    times++;
                    if (k == times || k == fn - times + 1)
                    {
                        printf("%lld\n", k == times ? gcd / i : i);
                        break;
                    }
                }
            }
        }
    }
    return 0;
}

Long Gcd(Long a, Long b)
{
    return b == 0 ? a : Gcd(b, a % b);
}

Long Factor(Long x)
{
    Long cnt = (Long)sqrt(x + 0.5) + 1;
    Long ans = 1;
    for (Long i=2; i<cnt; ++i)
    {
        if (x % i == 0)
        {
            Long temp = 0;
            while (x % i == 0)
            {
                x /= i;
                temp++;
            }
            ans *= 1 + temp;
        }
    }
    if (x > 1) ans *= 2;
    return ans;
}