結果

問題 No.3250 最小公倍数
コンテスト
ユーザー kotatsugame
提出日時 2025-08-30 08:32:30
言語 C++14
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 1,129 ms / 2,000 ms
コード長 1,033 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 784 ms
コンパイル使用メモリ 83,780 KB
実行使用メモリ 124,044 KB
最終ジャッジ日時 2025-11-09 23:16:46
合計ジャッジ時間 12,875 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 23
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘void dfs(int, int)’:
main.cpp:32:25: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
   32 |                 for(auto[q,c]:ret)
      |                         ^

ソースコード

diff #
raw source code 

#include<iostream>
#include<vector>
#include<map>
#include<cassert>
#include<atcoder/modint>
using namespace std;
using mint=atcoder::modint998244353;
int N,A[5<<17];
vector<int>G[5<<17];
int lsp[1<<20];
map<int,int>ret;
mint prod;
mint ans[5<<17];
void dfs(int u,int p)
{
	map<int,int>cur;
	mint pr=mint::raw(A[u]);
	{
		int a=A[u];
		while(a>1)
		{
			int q=lsp[a];
			int c=0;
			while(a%q==0)a/=q,c++;
			cur[q]=c;
		}
	}
	for(int v:G[u])if(v!=p)
	{
		dfs(v,u);
		if(cur.size()<ret.size())swap(cur,ret),swap(pr,prod);
		for(auto[q,c]:ret)
		{
			int t=cur[q];
			if(t<c)
			{
				cur[q]=c;
				for(int i=t;i<c;i++)pr*=mint::raw(q);
			}
		}
	}
	ans[u]=pr;
	swap(cur,ret);
	prod=pr;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	for(int i=2;i<1<<20;i++)if(lsp[i]==0)
	{
		for(int j=i;j<1<<20;j+=i)lsp[j]=i;
	}
	cin>>N;
	for(int i=0;i<N;i++)cin>>A[i];
	for(int i=1;i<N;i++)
	{
		int u,v;cin>>u>>v;u--,v--;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs(0,-1);
	for(int i=0;i<N;i++)cout<<ans[i].val()<<"\n";
}
0