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