結果
問題 |
No.2756 GCD Teleporter
|
ユーザー |
|
提出日時 | 2024-06-11 17:06:31 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,480 bytes |
コンパイル時間 | 2,170 ms |
コンパイル使用メモリ | 187,836 KB |
実行使用メモリ | 8,320 KB |
最終ジャッジ日時 | 2024-06-11 17:06:39 |
合計ジャッジ時間 | 8,067 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 WA * 3 |
other | AC * 20 WA * 16 |
コンパイルメッセージ
main.cpp: In function 'int main()': main.cpp:96:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions] 96 | for (auto [k, v] : F.get(a)) { | ^ main.cpp:105:14: warning: overflow in conversion from 'long long int' to 'int' changes value from '9223372036854775807' to '-1' [-Woverflow] 105 | int mi = LLONG_MAX; | ^~~~~~~~~ main.cpp:107:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions] 107 | for (auto [k, v] : F.get(A[i])) { | ^
ソースコード
#include <bits/stdc++.h> using namespace std; class Factorization { public: vector<int> L; Factorization(int N) { L.resize(N + 1); for (int i = 0; i <= N; ++i) { L[i] = i; } for (int i = 2; i <= N; ++i) { if (i != L[i]) continue; for (int j = 2 * i; j <= N; j += i) { L[j] = i; } } } vector<pair<int, int>> get(int n) { vector<pair<int, int>> D; if (n <= 1) return D; while (n != 1) { int cnt = 0; int now = L[n]; while (n % now == 0) { cnt++; n /= now; } D.push_back({now, cnt}); } return D; } }; class UnionFind { public: vector<int> par, rank, size; UnionFind(int n) { par.resize(n); rank.resize(n, 0); size.resize(n, 1); for (int i = 0; i < n; ++i) { par[i] = i; } } int find(int x) { if (par[x] == x) { return x; } else { return par[x] = find(par[x]); } } void union_sets(int x, int y) { x = find(x); y = find(y); if (x != y) { if (rank[x] < rank[y]) { swap(x, y); } if (rank[x] == rank[y]) { rank[x]++; } par[y] = x; size[x] += size[y]; } } bool is_same(int x, int y) { return find(x) == find(y); } int get_size(int x) { return size[find(x)]; } }; int main() { int N; cin >> N; vector<int> A(N); for (int i = 0; i < N; ++i) { cin >> A[i]; } const int M = 2 * 100000 + 5; Factorization F(M); int now = N; unordered_map<int, int> D; for (int a : A) { for (auto [k, v] : F.get(a)) { if (D.find(k) == D.end()) { D[k] = now; now++; } } } UnionFind U(now); int mi = LLONG_MAX; for (int i = 0; i < N; ++i) { for (auto [k, v] : F.get(A[i])) { mi = min(mi, k); U.union_sets(i, D[k]); } } set<int> S; for (int i = 0; i < N; ++i) { S.insert(U.find(i)); } if (mi == 2) { cout << (S.size() - 1) * 2 << endl; } else { cout << min(2 * S.size(), mi * (S.size() - 1)) << endl; } return 0; }