提出 #16398430

ソースコード 拡げる

#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");
}

提出情報

提出日時
問題 E - Coprime
ユーザ dnek
言語 C++ (GCC 9.2.1)
得点 500
コード長 969 Byte
結果 AC
実行時間 413 ms
メモリ 14860 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 500 / 500
結果
AC × 3
AC × 26
セット名 テストケース
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
ケース名 結果 実行時間 メモリ
hand_01.txt AC 16 ms 11048 KiB
max_01.txt AC 120 ms 14744 KiB
max_02.txt AC 362 ms 14860 KiB
max_03.txt AC 376 ms 14780 KiB
max_04.txt AC 413 ms 14768 KiB
max_05.txt AC 44 ms 11432 KiB
max_11.txt AC 76 ms 11520 KiB
max_12.txt AC 120 ms 14804 KiB
max_13.txt AC 47 ms 11208 KiB
max_14.txt AC 46 ms 11332 KiB
max_15.txt AC 42 ms 11432 KiB
max_16.txt AC 42 ms 11284 KiB
max_17.txt AC 47 ms 11436 KiB
max_18.txt AC 41 ms 11432 KiB
pair_01.txt AC 46 ms 11284 KiB
pair_02.txt AC 46 ms 11332 KiB
pair_03.txt AC 45 ms 11280 KiB
random_01.txt AC 40 ms 11084 KiB
random_02.txt AC 42 ms 11116 KiB
random_03.txt AC 50 ms 11012 KiB
random_04.txt AC 45 ms 11072 KiB
random_05.txt AC 42 ms 11356 KiB
random_06.txt AC 50 ms 11208 KiB
sample_01.txt AC 24 ms 11020 KiB
sample_02.txt AC 23 ms 11016 KiB
sample_03.txt AC 20 ms 10960 KiB