Submission #16325578


Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double


int main(){
    ll M = 1e6;
    vector<ll> table(M+1, 1);
    for (ll i = 2; i <= M; i++) {
        if (table[i] > 1) continue;
        for (ll j = i; j <= M; j += i) table[j] = i;
    }
    
    vector<ll> exist(M+1, 0), cnt(M+1, 0);
    bool ps = true;
    
    int N;
    cin >> N;
    for (int i = 0; i < N; i++) {
        ll A;
        cin >> A;
        while (A > 1) {
            ll p = table[A];
            if (exist[p] > 0) ps = false;
            exist[p] = 1;
            cnt[p]++;
            while (A%p == 0) A /= p;
        }
    }
    if (ps) {
        cout << "pairwise coprime\n";
        return 0;
    }
    for (int i = 2; i <= M; i++) {
        if (cnt[i] == N) {
            cout << "not coprime\n";
            return 0;
        }
    }
    cout << "setwise coprime\n";
	return 0;
}

Submission Info

Submission Time
Task E - Coprime
User hitoare
Language C++ (GCC 9.2.1)
Score 500
Code Size 941 Byte
Status AC
Exec Time 469 ms
Memory 26576 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
AC × 3
AC × 26
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All hand_01.txt, max_01.txt, max_02.txt, max_03.txt, max_04.txt, max_05.txt, max_11.txt, max_12.txt, max_13.txt, max_14.txt, max_15.txt, max_16.txt, max_17.txt, max_18.txt, pair_01.txt, pair_02.txt, pair_03.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, sample_01.txt, sample_02.txt, sample_03.txt
Case Name Status Exec Time Memory
hand_01.txt AC 39 ms 26416 KB
max_01.txt AC 134 ms 26444 KB
max_02.txt AC 447 ms 26572 KB
max_03.txt AC 469 ms 26348 KB
max_04.txt AC 454 ms 26504 KB
max_05.txt AC 62 ms 26424 KB
max_11.txt AC 110 ms 26420 KB
max_12.txt AC 129 ms 26560 KB
max_13.txt AC 64 ms 26532 KB
max_14.txt AC 64 ms 26404 KB
max_15.txt AC 72 ms 26472 KB
max_16.txt AC 70 ms 26404 KB
max_17.txt AC 74 ms 26536 KB
max_18.txt AC 75 ms 26532 KB
pair_01.txt AC 72 ms 26572 KB
pair_02.txt AC 64 ms 26448 KB
pair_03.txt AC 72 ms 26424 KB
random_01.txt AC 62 ms 26504 KB
random_02.txt AC 57 ms 26472 KB
random_03.txt AC 62 ms 26576 KB
random_04.txt AC 66 ms 26360 KB
random_05.txt AC 67 ms 26360 KB
random_06.txt AC 63 ms 26456 KB
sample_01.txt AC 30 ms 26508 KB
sample_02.txt AC 35 ms 26400 KB
sample_03.txt AC 37 ms 26568 KB