結果
問題 | No.2756 GCD Teleporter |
ユーザー |
![]() |
提出日時 | 2023-03-13 16:10:15 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 184 ms / 2,000 ms |
コード長 | 2,227 bytes |
コンパイル時間 | 4,600 ms |
コンパイル使用メモリ | 259,336 KB |
最終ジャッジ日時 | 2025-02-11 10:55:56 |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 36 |
ソースコード
#include<atcoder/all>using namespace atcoder;#include <bits/stdc++.h>template<class T> inline bool chmin(T&a, T b){if(a > b){a = b; return true;}else{return false;}}template<class T> inline bool chmax(T&a, T b){if(a < b){a = b; return true;}else{return false;}}#define ll long long#define double long double#define rep(i,n) for(int i=0;i<(n);i++)#define REP(i,n) for(int i=1;i<=(n);i++)#define mod (ll)(1e9+7)#define inf (ll)(3e18+7)#define eps (double)(1e-9)#define pi (double) acos(-1)#define all(x) x.begin(),x.end()#define rall(x) x.rbegin(),x.rend()using namespace std;struct smart_sieve{int n;vector<int> f;// 初期構築 : (nloglog(n))smart_sieve(int x = 1) :n(x), f(x+1, -1){for(ll i = 2; i <= n; i++){if(f[i] != -1)continue;for(ll j = i*i; j <= n; j += i){f[j] = (f[j] == -1 ? i : f[j]);}f[i] = i;}}// 素数判定 : O(1)bool isPrime(int x){return f[x] == x;}// 素因数分解 : O(log(n))vector<pair<ll,ll>> prime_factor(int x){if(x == 1)return {};vector<pair<ll, ll>> ret;ret.emplace_back(f[x], 1); x /= f[x];while(x != 1){if(f[x] == ret.back().first){ret.back().second++;}else{ret.emplace_back(f[x], 1);}x /= f[x];}return ret;}};int main(){int n;cin >> n;vector<int> a(n);rep(i, n)cin >> a[i];set<int> pf;smart_sieve ss(200000);rep(i, n){vector<pair<ll, ll>> p;p = ss.prime_factor(a[i]);for(auto x : p)pf.insert(x.first);}int cnt = 0, mn = mod;vector<int> pos(200000, -1);for(auto it = pf.begin(); it != pf.end(); it++){mn = (mn == mod ? (*it) : mn); pos[*it] = cnt++;}dsu uf(n+cnt);rep(i, n){vector<pair<ll, ll>> p;p = ss.prime_factor(a[i]);for(auto x : p)uf.merge(i, n+pos[x.first]);}set<int> st;rep(i, n)st.insert(uf.leader(i));int ans = mod, S = st.size();if(pos[2] == -1){ans = min(2*S, mn * (S-1));}else{ans = 2 * (S-1);}cout << ans << endl;}