結果

問題 No.3827 MST on LCM Graph
コンテスト
ユーザー shiomusubi496
提出日時 2026-11-10 17:49:45
言語 C++17
(gcc 15.3.0 + boost 1.92.0 + ACL)
コンパイル:
g++-15 -O2 -fplugin=/usr/lib/yukicoder/noavx512-gcc15.so -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 287 ms / 2,000 ms
+ 455µs
コード長 1,793 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,793 ms
コンパイル使用メモリ 322,748 KB
実行使用メモリ 105,076 KB
最終ジャッジ日時 2026-11-22 12:41:33
合計ジャッジ時間 9,939 ms
ジャッジサーバーID
(参考情報)
judge1_0 / judge4_0
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:1:9: warning: '#pragma once' in main file [-Wpragma-once-outside-header]
    1 | #pragma once
      |         ^~~~

ソースコード

diff #
raw source code

#pragma once
//# pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using ld=long double;
using ull=unsigned long long;
typedef pair<ll,ll> P;
#define vec vector
#define pb emplace_back
#define pcnt __builtin_popcountll
#define rep(i,n) for(ll i=0;i<(n);i++)
#define rng(i,s,t) for(ll i=s;i<t;i++)
#define len(a) int((a).size())
#define all(a) a.begin(),a.end()
#define compress(a) {sort(all(a));a.erase(unique(all(a)),a.end());}
constexpr ll INF=4e18;
constexpr ld EPS=1e-11;
template<typename T> bool chmin(T& a, T b){if(a > b){a = b; return true;} return false;}
template<typename T> bool chmax(T& a, T b){if(a < b){a = b; return true;} return false;}
template<typename itr> void printvec(itr begin, itr end) {
	for (itr p = begin; p < end; p++){
		if(p!=begin)cout<<" "; cout << *p;
	}
	cout << endl;
}
template <class T> T makevec(T value) {return value;}
template <class T, class... Args,
		std::enable_if_t<(sizeof...(Args) > 0), int> = 0>
auto makevec(std::size_t n, Args... args) {
	auto inner = makevec<T>(args...);
	return std::vector<decltype(inner)>(n, inner);
}

#include"atcoder/all"
using namespace atcoder;

int main(){
	ll n;
	cin>>n;
	vec<ll>a(n);
	rep(i,n)cin>>a[i];
	ll M=200000;
	vec<ll>cnt(M+1);
	rep(i,n)cnt[a[i]]++;
	ll ans=0;
	rep(i,M+1){
		if(cnt[i]>1){
			ans+=i*(cnt[i]-1);
			cnt[i]=1;
		}
	}
	vec<tuple<ll, ll, ll>> edge;
	for(ll g=1;g<=M;g++){
		ll z_g=INF;
		for(ll j=g;j<=M;j+=g){
			if(cnt[j]>0)chmin(z_g,j);
		}
		if(z_g!=INF){
			for(ll j=g;j<=M;j+=g){
				if(cnt[j]>0)edge.emplace_back(lcm(z_g,j),z_g,j);
			}
		}
	}
	sort(all(edge));
	dsu d(M+1);
	for(auto [t,u,v]: edge){
		if(d.same(u,v))continue;
		d.merge(u,v);
		ans+=t;
	}
	cout<<ans<<endl;
}
0