Weakened Common Divisor [Codeforces Round #505 B]

http://codeforces.com/contest/1025/problem/B

N個の数のペアから成る配列がある。
この配列のWCDを「全てのペアの少なくともどちらか片方の約数である数」とする。
WCDを1つ答えよ。
なければ-1

考察過程

1. GCDをもじってあるし、ペアの値も上限10^9なので、結局GCD使うんだろうという予想
2. 何のGCDを取ろうか考えると、A[i]*B[i]のGCDが意味を持ちそう
3. このGCDが答えっぽいが、反例がすぐに出てくる（反例：2,3と1,6）
4. このGCDが持つ意味を考えてみると、このGCDの約数にWCDがあることがわかる
5. 求めたGCDを使いながら、各ペアでGCDが1にならないように取ってみる
6. それっぽいので投げるとAC

解法

http://codeforces.com/contest/1025/submission/41896884

まず、全てのペアについてA[i]*B[i]のGCDを取る。
その後、全てのペアについて、どちらの値を使うか確定するために、GCDが1にならないようにどちらかを選んで行く。
貪欲にやってGCD=1となれば、答えは無い。

int N, A[151010], B[151010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i] >> B[i];

    ll g = 0;
    rep(i, 0, N) g = gcd(g, 1LL * A[i] * B[i]);

    rep(i, 0, N) {
        if (gcd(g, A[i]) == 1) g = gcd(g, B[i]);
        else g = gcd(g, A[i]);
    }

    if (g == 1) g = -1;
    printf("%lld\n", g);
}