結果

問題 No.3250 最小公倍数
コンテスト
ユーザー nururi
提出日時 2025-09-18 23:16:11
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 1,245 bytes
コンパイル時間 3,510 ms
コンパイル使用メモリ 288,376 KB
実行使用メモリ 822,124 KB
最終ジャッジ日時 2025-10-16 17:09:59
合計ジャッジ時間 11,435 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 1
other MLE * 1 -- * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

const int N = 500000;
const long mod = 998244353;

bool seen[N];
vector<int> path[N];
map<long, int> mp[N];
long ans[N];

void dfs(int cur){
  seen[cur] = true;
  
  vector<int> child;
  for(auto next:path[cur]){
    if(!seen[next]) child.emplace_back(next);
  }
  for(auto next:child) dfs(next);
  
  for(auto i:child){
    for(auto x:mp[i]){
      int cnt = x.second - mp[cur][x.first];
      for(int j=0; j<cnt; j++){
        ans[cur] = ans[cur] * (x.first) % mod;
      }
      if(cnt>0) mp[cur][x.first] += cnt;
    }
  }
}

int main(){
  int n;
  cin >> n;
  
  vector<int> prime;
  for(int i=2; i<=1000; i++){
    bool is_prime = true;
    for(int p=2; p*p<=i; p++){
      if(i%p == 0){
        is_prime = false;
        break;
      }
    }
    if(is_prime) prime.emplace_back(i);
  }
  
  for(int i=0; i<n; i++){
    long a;
    cin >> a;
    ans[i] = a;
    for(auto p:prime){
      while(a%p==0){
        mp[i][p]++;
        a /= p;
      }
    }
    if(a>1) mp[i][a]++;
  }
  
  for(int i=0; i<n-1; i++){
    int u, v;
    cin >> u >> v;
    u--, v--;
    path[u].emplace_back(v);
    path[v].emplace_back(u);
  }
  
  dfs(0);
  for(int i=0; i<n; i++){
    cout << ans[i] << endl;
  }
}
0