Submission #16398430


Source Code Expand

Copy
#include <bits/stdc++.h>
#define each(i, a) for (auto &&i : (a))
using namespace std;

using vi = vector<int>;
using seti = set<int>;

template <class T>
void COUT(const T &x) { cout << x << endl; }

struct prime_factors_osa_k {
  vi spf; // smallest prime factor
  prime_factors_osa_k(int n): spf(n + 1) {
    spf[1] = 1;
    for (int i = 0; i <= n; i++) spf[i] = i;
    for (int i = 2; i * i <= n; i++) if (spf[i] == i)
      for (int j = i * i; j <= n; j += i)
        if (spf[j] == j) spf[j] = i;
  }
  seti operator()(int x) {
    seti ret;
    while (x != 1) {
      ret.insert(spf[x]);
      x = x / spf[x];
    }
    return ret;
  }
} prime_factors(1000000);

int main() {
  int N;
  cin >> N;
  vi A(N);
  each(x, A) cin >> x;

  vi cnt(1000001);
  each(x, A) each(f, prime_factors(x)) cnt[f]++;
  int mx = 1;
  each(x, cnt) if (mx < x) mx = x;

  if (mx == 1) COUT("pairwise coprime");
  else if (mx < N) COUT("setwise coprime");
  else COUT("not coprime");
}

Submission Info

Submission Time
Task E - Coprime
User dnek
Language C++ (GCC 9.2.1)
Score 500
Code Size 969 Byte
Status
Exec Time 413 ms
Memory 14860 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
× 3
× 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 16 ms 11048 KB
max_01.txt 120 ms 14744 KB
max_02.txt 362 ms 14860 KB
max_03.txt 376 ms 14780 KB
max_04.txt 413 ms 14768 KB
max_05.txt 44 ms 11432 KB
max_11.txt 76 ms 11520 KB
max_12.txt 120 ms 14804 KB
max_13.txt 47 ms 11208 KB
max_14.txt 46 ms 11332 KB
max_15.txt 42 ms 11432 KB
max_16.txt 42 ms 11284 KB
max_17.txt 47 ms 11436 KB
max_18.txt 41 ms 11432 KB
pair_01.txt 46 ms 11284 KB
pair_02.txt 46 ms 11332 KB
pair_03.txt 45 ms 11280 KB
random_01.txt 40 ms 11084 KB
random_02.txt 42 ms 11116 KB
random_03.txt 50 ms 11012 KB
random_04.txt 45 ms 11072 KB
random_05.txt 42 ms 11356 KB
random_06.txt 50 ms 11208 KB
sample_01.txt 24 ms 11020 KB
sample_02.txt 23 ms 11016 KB
sample_03.txt 20 ms 10960 KB