結果
問題 | No.2756 GCD Teleporter |
ユーザー | hato336 |
提出日時 | 2024-05-10 22:18:43 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,088 ms / 2,000 ms |
コード長 | 7,435 bytes |
コンパイル時間 | 5,497 ms |
コンパイル使用メモリ | 325,852 KB |
実行使用メモリ | 18,148 KB |
最終ジャッジ日時 | 2024-05-10 22:19:09 |
合計ジャッジ時間 | 24,206 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 4 ms
7,924 KB |
testcase_01 | AC | 5 ms
7,948 KB |
testcase_02 | AC | 4 ms
7,944 KB |
testcase_03 | AC | 3 ms
7,996 KB |
testcase_04 | AC | 47 ms
8,356 KB |
testcase_05 | AC | 198 ms
10,084 KB |
testcase_06 | AC | 577 ms
13,756 KB |
testcase_07 | AC | 435 ms
12,560 KB |
testcase_08 | AC | 402 ms
12,324 KB |
testcase_09 | AC | 366 ms
11,660 KB |
testcase_10 | AC | 499 ms
13,512 KB |
testcase_11 | AC | 667 ms
14,644 KB |
testcase_12 | AC | 132 ms
9,312 KB |
testcase_13 | AC | 658 ms
14,448 KB |
testcase_14 | AC | 650 ms
13,992 KB |
testcase_15 | AC | 135 ms
9,252 KB |
testcase_16 | AC | 332 ms
11,272 KB |
testcase_17 | AC | 423 ms
12,052 KB |
testcase_18 | AC | 127 ms
9,216 KB |
testcase_19 | AC | 685 ms
14,596 KB |
testcase_20 | AC | 795 ms
13,384 KB |
testcase_21 | AC | 355 ms
10,544 KB |
testcase_22 | AC | 609 ms
13,604 KB |
testcase_23 | AC | 93 ms
8,676 KB |
testcase_24 | AC | 638 ms
12,552 KB |
testcase_25 | AC | 670 ms
12,700 KB |
testcase_26 | AC | 634 ms
13,336 KB |
testcase_27 | AC | 600 ms
13,616 KB |
testcase_28 | AC | 312 ms
11,232 KB |
testcase_29 | AC | 467 ms
12,680 KB |
testcase_30 | AC | 648 ms
14,228 KB |
testcase_31 | AC | 264 ms
10,748 KB |
testcase_32 | AC | 978 ms
12,572 KB |
testcase_33 | AC | 363 ms
9,988 KB |
testcase_34 | AC | 73 ms
8,604 KB |
testcase_35 | AC | 530 ms
13,216 KB |
testcase_36 | AC | 322 ms
12,776 KB |
testcase_37 | AC | 5 ms
8,012 KB |
testcase_38 | AC | 1,088 ms
13,524 KB |
testcase_39 | AC | 1,020 ms
18,148 KB |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using namespace atcoder; #define all(...) std::begin(__VA_ARGS__), std::end(__VA_ARGS__) #define rall(...) std::rbegin(__VA_ARGS__), std::rend(__VA_ARGS__) #define OVERLOAD_REP(_1, _2, _3, _4, name, ...) name #define REP1(n) for(ll i=0;i<n;i++) #define REP2(i, n) for (ll i=0;i<n;i++) #define REP3(i, a, n) for (ll i=a;i<n;i++) #define REP4(i, a, b, n) for(ll i=a;i<n;i+=b) #define rep(...) OVERLOAD_REP(__VA_ARGS__, REP4, REP3, REP2, REP1)(__VA_ARGS__) #define OVERLOAD_RREP(_1, _2, _3, _4, name, ...) name #define RREP1(n) for(ll i=n-1;i>=0;i--) #define RREP2(i, n) for(ll i=n-1;i>=0;i--) #define RREP3(i, a, n) for(ll i=n-1;i>=a;i--) #define RREP4(i, a, b, n) for(ll i=n-1;i>=a;i-=b) #define rrep(...) OVERLOAD_RREP(__VA_ARGS__, RREP4, RREP3, RREP2, RREP1)(__VA_ARGS__) #define foa(a,v) (auto& a : (v)) #define uniq(a) sort(all(a));a.erase(unique(all(a)),end(a)) #define len(n) (long long)(n).size() #define pb push_back using ll = long long; using ld = long double; using ull = unsigned long long; using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>; using vll = vector<ll>; using vvll = vector<vll>; using vvvll = vector<vvll>; using vs = vector<string>; using vvs = vector<vs>; using vvvs = vector<vvs>; using vld = vector<ld>; using vvld = vector<vld>; using vvvld = vector<vvld>; using vc = vector<char>; using vvc = vector<vc>; using vvvc = vector<vvc>; using pll = pair<ll,ll>; using vpll = vector<pll>; template<class... T> constexpr auto min(T... a){ return min(initializer_list<common_type_t<T...>>{a...}); } template<class... T> constexpr auto max(T... a){ return max(initializer_list<common_type_t<T...>>{a...}); } template<class... T> void input(T&... a){ (cin >> ... >> a); } ll POW(ll a,ll b){ ll ans = 1; while (b){ if (b & 1){ ans *= a; } a *= a; b /= 2; } return ans; } ll MODPOW(ll a,ll b,ll c){ ll ans = 1; while (b){ if (b & 1){ ans *= a; ans %= c; } a *= a; a %= c; b /= 2; } return ans; } #define OVERLOAD_POW(_1, _2, _3, name, ...) name #define pow(...) OVERLOAD_POW(__VA_ARGS__, MODPOW, POW)(__VA_ARGS__) #define INT(...) int __VA_ARGS__; input(__VA_ARGS__) #define LL(...) ll __VA_ARGS__; input(__VA_ARGS__) #define ULL(...) ull __VA_ARGS__; input(__VA_ARGS__) #define LD(...) ld __VA_ARGS__; input(__VA_ARGS__) #define STR(...) string __VA_ARGS__; input(__VA_ARGS__) #define CHA(...) char __VA_ARGS__; input(__VA_ARGS__) #define VLL(name,length) vll name(length);rep(i,length){cin >> name[i];} #define VVLL(name,h,w) vvll name(h,vll(w));rep(i,h)rep(j,w){cin >> name[i][j];} #define VVVLL(name,a,b,c) vvvll name(a,vvll(b,vll(c)));rep(i,a)rep(j,b)rep(k,c){cin >> name[i][j][k];} #define VI(name,length) vi name(length);rep(i,length){cin >> name[i];} #define VVI(name,h,w) vvi name(h,vi(w));rep(i,h)rep(j,w){cin >> name[i][j];} #define VVVI(name,a,b,c) vvvi name(a,vvll(b,vi(c)));rep(i,a)rep(j,b)rep(k,c){cin >> name[i][j][k];} #define VLD(name,length) vld name(length);rep(i,length){cin >> name[i];} #define VVLD(name,h,w) vvld name(h,vld(w));rep(i,h)rep(j,w){cin >> name[i][j];} #define VVVLD(name,a,b,c) vvvld name(a,vvld(b,vld(c)));rep(i,a)rep(j,b)rep(k,c){cin >> name[i][j][k];} #define VC(name,length) vc name(length);rep(i,length){cin >> name[i];} #define VVC(name,h,w) vvc name(h,vc(w));rep(i,h)rep(j,w){cin >> name[i][j];} #define VVVC(name,a,b,c) vvvc name(a,vvc(b,vc(c)));rep(i,a)rep(j,b)rep(k,c){cin >> name[i][j][k];} #define VS(name,length) vs name(length);rep(i,length){cin >> name[i];} #define VVS(name,h,w) vvs name(h,vs(w));rep(i,h)rep(j,w){cin >> name[i][j];} #define VVVS(name,a,b,c) vvvs name(a,vvs(b,vs(c)));rep(i,a)rep(j,b)rep(k,c){cin >> name[i][j][k];} #define PLL(name) pll name;cin>>name.first>>name.second; #define VPLL(name,length) vpll name(length);rep(i,length){cin>>name[i].first>>name[i].second;} void print(){cout << "\n";} template<class T, class... Ts> void print(const T& a, const Ts&... b){cout << a;(cout << ... << (cout << ' ', b));cout << '\n';} void print(vll x){rep(i,len(x)){cout << x[i];if(i!=len(x)-1){cout << " ";}else{cout << '\n';}}} void print(vvll x){rep(i,len(x))rep(j,len(x[i])){cout << x[i][j];if(j!=len(x[i])-1){cout << " ";}else{cout << '\n';}}} void print(vi x){rep(i,len(x)){cout << x[i];if(i!=len(x)-1){cout << " ";}else{cout << '\n';}}} void print(vvi x){rep(i,len(x))rep(j,len(x[i])){cout << x[i][j];if(j!=len(x[i])-1){cout << " ";}else{cout << '\n';}}} void print(vvvi x){rep(i,len(x))rep(j,len(x[i]))rep(k,len(x[i][j])){cout << x[i][j][k];if(k!=len(x[i][j])-1){cout << " ";}else if(j!=len(x[i])-1){cout << " | ";}else{cout << '\n';}}} void print(vld x){rep(i,len(x)){cout << x[i];if(i!=len(x)-1){cout << " ";}else{cout << '\n';}}} void print(vvld x){rep(i,len(x))rep(j,len(x[i])){cout << x[i][j];if(j!=len(x[i])-1){cout << " ";}else{cout << '\n';}}} void print(vvvld x){rep(i,len(x))rep(j,len(x[i]))rep(k,len(x[i][j])){cout << x[i][j][k];if(k!=len(x[i][j])-1){cout << " ";}else if(j!=len(x[i])-1){cout << " | ";}else{cout << '\n';}}} void print(vc x){rep(i,len(x)){cout << x[i];if(i!=len(x)-1){cout << " ";}else{cout << '\n';}}} void print(vvc x){rep(i,len(x))rep(j,len(x[i])){cout << x[i][j];if(j!=len(x[i])-1){cout << " ";}else{cout << '\n';}}} void print(vvvc x){rep(i,len(x))rep(j,len(x[i]))rep(k,len(x[i][j])){cout << x[i][j][k];if(k!=len(x[i][j])-1){cout << " ";}else if(j!=len(x[i])-1){cout << " | ";}else{cout << '\n';}}} void print(vs x){rep(i,len(x)){cout << x[i];if(i!=len(x)-1){cout << " ";}else{cout << '\n';}}} void print(vvs x){rep(i,len(x))rep(j,len(x[i])){cout << x[i][j];if(j!=len(x[i])-1){cout << " ";}else{cout << '\n';}}} void print(vvvs x){rep(i,len(x))rep(j,len(x[i]))rep(k,len(x[i][j])){cout << x[i][j][k];if(k!=len(x[i][j])-1){cout << " ";}else if(j!=len(x[i])-1){cout << " | ";}else{cout << '\n';}}} void print(pll x){cout << x.first << x.second << '\n';} void print(vpll x){rep(i,len(x)){cout << x[i].first << x[i].second << '\n';}} //キーに素因数,値に何乗かを格納した連想配列を返すタイプ template<class T> map<T,T>prime_factorization(T N){ map<T,T> ans; T X=N; for(T i=2;i*i<=N;i++){ if(X%i!=0)continue; if(X==1)break; while(X%i==0){ ans[i]++; X/=i; } } if(X!=1)ans[X]++; return ans; } //素因数を配列に詰めたタイプ template<class T> vector<T>prime_factorization2(T N){ vector<T> ans; T X=N; for(T i=2;i*i<=N;i++){ if(X%i!=0)continue; if(X==1)break; while(X%i==0){ ans.push_back(i); X/=i; } } if(X!=1)ans.push_back(X); return ans; } int main(){ LL(n); VLL(a,n); ll ans = 1000000000000000000; dsu uf(n); vvll c(200000+10); rep(i,n){ vll x = prime_factorization2(a[i]); sort(all(x)); x.erase(unique(all(x)),x.end()); rep(j,len(x)){ c[x[j]].push_back(i); ans = min(ans,x[j]); } } rep(i,200000+10){ if(len(c[i]) == 0){ continue; } rep(j,len(c[i])-1){ uf.merge(c[i][j],c[i][j+1]); } } ll cnt = 0; rep(i,n){ if(uf.leader(i) == i){ cnt++; } } cout << min(ans * (cnt-1),2*cnt); }