結果

問題 No.3250 最小公倍数
ユーザー Taiki0715
提出日時 2025-08-30 15:01:08
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,693 ms / 2,000 ms
コード長 2,194 bytes
コンパイル時間 1,633 ms
コンパイル使用メモリ 120,024 KB
実行使用メモリ 81,664 KB
最終ジャッジ日時 2025-08-30 15:01:28
合計ジャッジ時間 17,303 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
using ll=long long;
constexpr ll mod=998244353;
vector<int>lpf;
ll pow_mod(ll x,ll p){
  if(p==1)return x;
  ll res=1;
  while(p){
    if(p&1)res=(res*x)%mod;
    x=(x*x)%mod;
    p>>=1;
  }
  return res;
}
void init(int n){
  lpf.resize(n+1,-1);
  for(int i=2;i<=n;i++)if(lpf[i]==-1){
    for(int j=1;i*j<=n;j++)if(lpf[i*j]==-1){
      lpf[i*j]=i;
    }
  }
}
vector<pair<int,int>>factorize(int n){
  vector<pair<int,int>>res;
  while(n>1){
    int p=lpf[n];
    int e=0;
    while(n%p==0){
      n/=p;
      e++;
    }
    res.emplace_back(p,e);
  }
  return res;
}
int main(){
  int n;
  cin>>n;
  vector<int>a(n);
  for(int i=0;i<n;i++)cin>>a[i];
  init(*max_element(a.begin(),a.end()));
  vector<vector<int>>g(n);
  for(int i=0;i<n-1;i++){
    int u,v;
    cin>>u>>v;
    u--,v--;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  g[0].push_back(-1);
  auto hld=[&](auto self,int x,int p)->int {
    int res=1;
    int mx=-1;
    for(int&c:g[x]){
      if(c==p){
        if(g[x].back()==c)break;
        swap(g[x].back(),c);
      }
      int sz=self(self,c,x);
      if(mx<sz){
        mx=sz;
        swap(g[x][0],c);
      }
      res+=sz;
    }
    g[x].pop_back();
    return res;
  };
  hld(hld,0,-1);
  vector<vector<pair<int,int>>>a_fac(n);
  for(int i=0;i<n;i++)a_fac[i]=factorize(a[i]);
  vector<ll>ans(n);
  ll now=1;
  vector<ll>pe(lpf.size());
  auto set=[&](auto self,int x)->void {
    for(auto [p,e]:a_fac[x]){
      if(pe[p]>=e)continue;
      now=(now*pow_mod(p,e-pe[p]))%mod;
      pe[p]=e;
    }
    for(int c:g[x])self(self,c);
  };
  auto reset=[&](auto self,int x)->void {
    for(auto [p,e]:a_fac[x])pe[p]=0;
    for(int c:g[x])self(self,c);
  };
  auto dfs=[&](auto self,int x)->void {
    for(int i=1;i<ssize(g[x]);i++){
      self(self,g[x][i]);
      reset(reset,g[x][i]);
      now=1;
    }
    if(!g[x].empty())self(self,g[x][0]);
    for(int i=1;i<ssize(g[x]);i++)set(set,g[x][i]);
    for(auto [p,e]:a_fac[x]){
      if(pe[p]>=e)continue;
      now=(now*pow_mod(p,e-pe[p]))%mod;
      pe[p]=e;
    }
    ans[x]=now;
  };
  dfs(dfs,0);
  for(int i=0;i<n;i++)cout<<ans[i]<<'\n';
}
0