結果

問題 No.2756 GCD Teleporter
コンテスト
ユーザー ttkkggww
提出日時 2024-05-22 17:36:10
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 638 ms / 2,000 ms
コード長 1,599 bytes
コンパイル時間 4,319 ms
コンパイル使用メモリ 258,232 KB
最終ジャッジ日時 2025-02-21 16:26:38
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#include <vector>
using namespace std;
#include<atcoder/all>
using namespace atcoder;
using ll = long long;
int N;
vector<int> A;

vector<int> prime_factor(int n){
	vector<int> res;
	for(int i = 2; i*i <= n; i++){
		if(n%i==0){
			res.push_back(i);
		}
		while(n%i==0){
			n /= i;
		}
	}
	if(n!=1) res.push_back(n);
	return res;
}

void solve(){
	dsu UF(N);
	vector<int> is2(N, 0);
	vector<int> is3(N, 0);
	for(int i = 0;i<N;i++){
		if(A[i]%2==0) is2[i] = 1;
		if(A[i]%3==0) is3[i] = 1;
	}
	vector<vector<int>> factindex(202020);
	for(int i = 0;i<N;i++){
		auto fact = prime_factor(A[i]);
		for(auto x:fact){
			factindex[x].push_back(i);
		}
	}
	for(int i = 0;i<202020;i++){
		for(int j = 1;j<(int)factindex[i].size();j++){
			int lleader = UF.leader(factindex[i][0]);
			int rleader = UF.leader(factindex[i][j]);
			is2[lleader] |= is2[rleader];
			is2[rleader] |= is2[lleader];
			is3[lleader] |= is3[rleader];
			is3[rleader] |= is3[lleader];
			UF.merge(factindex[i][0], factindex[i][j]);
		}
	}
	auto vv = UF.groups();
	int is2count = 0;
	int is3count = 0;
	for(auto &v:vv){
		int lleader = UF.leader(v[0]);
		is2count += is2[lleader];
		is3count += is3[lleader];
	}
	if(vv.size()==1){
		cout<<0<<endl;
		return;
	}

	if(is2count==0&&is3count==0){
		cout<<vv.size()*2<<endl;
	}else if(is2count==0){
		if(vv.size()==2){
			cout<<3<<endl;
		}else{
			cout<<vv.size()*2<<endl;
		}
	}else{
		cout<<vv.size()*2-2<<endl;
	}
}

signed main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cin >> N;
	A.resize(N);
	for(int i = 0; i < N; i++){
		cin >> A[i];
	}
	solve();
}
0