Submission #16398430

---

Source Code Expand

#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

Judge Result