結果

問題 No.3250 最小公倍数
コンテスト
ユーザー Gu Jie
提出日時 2026-10-16 18:42:16
言語 C++23(gcc16)
(gcc 16.2.0 + boost 1.92.0 + ACL)
コンパイル:
g++-16 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 1,735 ms / 2,000 ms
+ 372µs
コード長 3,213 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 5,420 ms
コンパイル使用メモリ 359,756 KB
実行使用メモリ 229,304 KB
最終ジャッジ日時 2026-10-16 18:42:59
合計ジャッジ時間 30,341 ms
ジャッジサーバーID
（参考情報） 		judge5_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 23
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'void artidfs(ll)':
main.cpp:58:34: warning: 'loc' may be used uninitialized [-Wmaybe-uninitialized]
   58 |                 val[node]=val[loc];
      |                           ~~~~~~~^
main.cpp:46:18: note: 'loc' was declared here
   46 |         ll now=0,loc,mul=1;
      |                  ^~~

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll biao=1e6+10,mod=998244353;
vector<ll> e[biao],v[biao];
ll dfn[biao],n,st[biao][20],d[biao],a[biao],idx,to[biao];
vector<ll> rd[biao],pri;
ll vis[biao];
ll val[biao],mx[biao];

void dfs(ll node,ll father){
	d[node]=d[father]+1,st[node][0]=father,dfn[node]=++idx,to[dfn[node]]=node;
	for(ll i=1;i<19;i++) st[node][i]=st[st[node][i-1]][i-1];
	for(ll i=0;i<v[node].size();i++){
		ll j=v[node][i];
		if(j==father) continue;
		dfs(j,node);
	}
}

ll lca(ll x,ll y){
	if(d[x]<d[y]) swap(x,y);
	for(ll i=18;i>=0;i--) if(d[st[x][i]]>=d[y]) x=st[x][i];
	if(x==y) return x;
	for(ll i=18;i>=0;i--) if(st[x][i]!=st[y][i]) x=st[x][i],y=st[y][i];
	return st[x][0];
}

bool cmp(ll x1,ll x2){return dfn[x1]<dfn[x2];}

ll s[biao];
ll ans[biao],qp[biao];

ll quickpow(ll x,ll y){
	ll ret=1;
	while(y){
		if(y&1) ret=ret*x%mod;
		x=x*x%mod,y>>=1;
	}
	return ret;
}

void artidfs(ll node){
//	cout<<node<<'\n';
	ll now=0,loc,mul=1;
	for(ll i=0;i<e[node].size();i++){
		ll j=e[node][i];
		artidfs(j);
		mul=mul*qp[j]%mod;
		if(mx[j]>now) now=mx[j],loc=j;
	}
	if(mx[node]>now){
		ans[node]=ans[node]*mul%mod*val[node]%mod;
	}
	else{
		mx[node]=now;
		val[node]=val[loc];
		qp[node]=qp[loc];
		ans[node]=ans[node]*mul%mod*val[loc]%mod;
	}
	e[node].clear();
}

void link(ll x,ll y){
	val[x]=qp[x]=1,mx[x]=0;
	val[y]=qp[y]=1,mx[y]=0;
	e[x].push_back(y);
}

void solve(ll p){
//	cout<<p<<":\n";
	if(rd[p].empty()) return;
	ll np=quickpow(p,mod-2);
	ll sz=0;
	for(ll i=0;i<rd[p].size();i++){
		ll j=rd[p][i];
		if(!sz){s[++sz]=j;continue;}
		
		ll l=lca(j,s[sz]);
		while(sz>=2 && d[s[sz-1]]>=d[l]) link(s[sz-1],s[sz]),sz--;
		
		if(s[sz]!=l){
			link(l,s[sz]);
			sz--;
			if(!sz || s[sz]!=l) s[++sz]=l;
		}
		s[++sz]=j;
	}
	ll rt=s[1];
	val[rt]=qp[rt]=1,mx[rt]=0;
	while(sz>=2) link(s[sz-1],s[sz]),sz--;
	
	for(ll i=0;i<rd[p].size();i++){
		ll tmp=a[rd[p][i]],j=rd[p][i];
		while(tmp%p==0) mx[j]++,val[j]=val[j]*p%mod,qp[j]=qp[j]*np%mod,tmp/=p;
	}
	
//	cout<<p<<" "<<rt<<"***\n";
//	for(ll i=1;i<=n;i++){
//		cout<<i<<":"<<mx[i]<<" "<<val[i]<<" "<<qp[i]<<"->"<<'\n';
//		for(ll j=0;j<e[i].size();j++) cout<<e[i][j]<<" ";cout<<'\n';
//	}
	
//	cout<<rt<<'\n';
	artidfs(rt);
}

void query(ll node,ll father){
	for(ll i=0;i<v[node].size();i++){
		ll j=v[node][i];
		if(j==father) continue;
		query(j,node);
		ans[node]=ans[node]*ans[j]%mod;
	}
}

int main(){

	
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	for(ll i=2;i<=1e6;i++){
		if(!vis[i]) pri.push_back(i);
		for(ll j=0;j<pri.size();j++){
			if(i*pri[j]>1e6) break;
			vis[i*pri[j]]=1;
			if(i%pri[j]==0) break;
		}
	}
	
	cin>>n;
	for(ll i=1;i<=n;i++) cin>>a[i];
	for(ll i=1;i<n;i++){
		ll x,y;
		cin>>x>>y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	dfs(1,0);
	
	for(ll i=1;i<=n;i++){
		ll tmp=a[to[i]];
		for(ll j=0;j<pri.size();j++){
			if(pri[j]>1e3) break;
			if(tmp%pri[j]) continue;
			while(tmp%pri[j]==0) tmp/=pri[j];
			rd[pri[j]].push_back(to[i]);
		}
		if(tmp!=1) rd[tmp].push_back(to[i]);
	}
	
	for(ll i=1;i<=n;i++) ans[i]=1;
	for(ll i=0;i<pri.size();i++) solve(pri[i]);
//	for(ll i=1;i<=n;i++) cout<<ans[i]<<'\n';
	query(1,0);
	for(ll i=1;i<=n;i++) cout<<ans[i]<<'\n';
	
	return 0;
}
0