[AtCoder] ABC 177 E – Coprime

2020年8月30日2020年12月13日

問題

方針

\( N \) 個の整数が 'pairwise coprime’ であれば 'setwise coprime’ なので、’pairwise coprime’かどうかを先に調べます。\( N \) 個の整数において、\( i \ ( 2 \leq i \leq 10^6)\) の倍数の数が \( 1 \) 以下であれば 'pairwise coprime’ であると言えます。次に、\( i \) の倍数が \( N \) 個あるとき、’not coprime’となります。そうでなければ、’setwise coprime’ となります。

したがって、\( i \) の倍数の個数を \( B_i \) として、この配列を全探索します。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAX = 1000000;
int B[MAX + 1]{};

int main() {
    int N;
    cin >> N;
    int A[N];

    for (int i = 0; i < N; i++) {
        cin >> A[i];
        B[A[i]]++;
    }
    bool flag1 = true;
    bool flag2 = true;
    for (int i = 2; i <= MAX; i++) {
        int cnt = 0;
        for (int j = 1; j < MAX; j++) {
            if (i * j > MAX) break;
            cnt += B[i * j];
        }
        if (cnt > 1) {
            flag1 = false;
        }
        if (cnt == N) {
            flag2 = false;
        }
    }
    if (flag1) {
        cout << "pairwise coprime\n";
    } else if (flag2) {
        cout << "setwise coprime\n";
    } else {
        cout << "not coprime\n";
    }
    return 0;
}