Revenge of GCD

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long LL;

LL gcd(LL a, LL b) {
    return b ? gcd(b, a % b) : a;
}

int main() {
    int t;
    cin >> t;
    vector<LL> v;

    while (t -- ) {
        v.clear();
        LL x, y, k;
        cin >> x >> y >> k;
        LL g = gcd(x, y);

        for (LL i = 1; i * i <= g; i ++ )

            if (g % i == 0) {
                v.push_back(i);

                if (i * i != g)
                    v.push_back(g / i);
            }

        sort(v.begin(), v.end());

        if (v.size() < k)
            puts("-1");
        else
            printf("%lld\n", v[v.size() - k]);
    }

    return 0;
}

GCD

#include <iostream>

using namespace std;

typedef long long LL;

int phi(int x) {
    int res = x;

    for (int i = 2; i <= x / i; i ++ )

        if (x % i == 0) {
            res = res / i * (i - 1);

            while (x % i == 0)
                x /= i;
        }

    if (x > 1)
        res = res / x * (x - 1);
    return res;
}

int main() {
    int t;
    cin >> t;

    while (t -- ) {
        LL res = 0;
        int n, m;
        cin >> n >> m;

        for (int i = 1; n / i >= m; i ++ )

            if (n % i == 0)
                res += phi(i);
        cout << res << endl;
    }

    return 0;
}

最大的最大公约数

#include <iostream>

using namespace std;

const int N = 1e6 + 10;

int st[N];

int main() {
    int n;
    cin >> n;
    int MAX = 0;

    while (n -- ) {
        int m;
        cin >> m;
        st[m] ++ ;
        MAX = max(MAX, m);
    }

    int ans = 0;

    for (int i = MAX; i > 0; i --) {

        int cnt = 0;

        for (int j = i; j < N; j += i) {

            cnt += st[j];

            if (cnt >= 2)
                break;
        }

        if (cnt >= 2) {
            ans = i;
            break;
        }
    }

    cout << ans << endl;
    return 0;
}