Chokudai SpeedRun 002 J問題：GCD β

問題. GCD β

自然数のペアが 個与えられる． 番目のペアは である．各ペアからちょうど1つの自然数を選んでそれらの最大公約数をとる．このときの考えられる最大公約数の最大値を求めよ．

制約： ，　

解法

最大公約数は素因数分解をしたときの各素数の指数の最小値の積となる（cf. 最大公約数 - Wikipedia）．したがって， を選んだ時は2番目以降のペアのどんな選び方に対しても得られる最大公約数の最大値は のある約数となる．同様に を選んだときの得られる最大公約数の最大値は のある約数となる．したがって， または の約数 に対して，任意の で または が で割り切れるかを判定して，割り切れるよな約数の最大値が答えとなる．

計算時間： （ただし， は と の約数の個数の最大値；）

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

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

bool check(ll g, const vector<ll> &a, const vector<ll> &b) {
    for (size_t i = 1; i < a.size(); ++i)
        if ((a[i] % g != 0) || (b[i] % g != 0)) return false;
    return true;
}

int main() {
    cin.tie(0); ios::sync_with_stdio(false);

    int n;
    cin >> n;

    vector<ll> a(n), b(n);
    for (int i = 0; i < n; ++i) cin >> a[i] >> b[i];

    ll max_g = 0;
    for (ll x = 1; x * x <= a[0]; ++x) {
        if (a[0] % x != 0) continue;
        if (check(x, a, b)) max_g = max(max_g, x);
        if (x * x != a[0] && check(a[0] / x, a, b))
            max_g = max(max_g, a[0] / x);
    }
    for (ll x = 1; x * x <= b[0]; ++x) {
        if (b[0] % x != 0) continue;
        if (check(x, a, b)) max_g = max(max_g, x);
        if (x * x != b[0] && check(b[0] / x, a, b))
            max_g = max(max_g, b[0] / x);
    }

    cout << max_g << '\n';

    return 0;
}

全然分からないで悩んでいた．解法が思いついた後は，何で思いつかないんだ！自明だ！！という気分になるのよくない．