結果

問題 No.3250 最小公倍数
ユーザー nururi
提出日時 2025-09-18 18:57:57
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,061 bytes
コンパイル時間 3,025 ms
コンパイル使用メモリ 290,456 KB
実行使用メモリ 325,760 KB
最終ジャッジ日時 2025-09-18 18:58:31
合計ジャッジ時間 32,053 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 17 TLE * 1 -- * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

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

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

unordered_map<long, int> dfs(int cur){
  seen[cur] = true;
  
  vector<unordered_map<long, int>> child;
  for(auto next:path[cur]){
    if(!seen[next]) child.push_back(dfs(next));
  }
  
  for(auto x:child){
    for(auto y:x){
      ans[cur][y.first] = max(ans[cur][y.first], y.second);
    }
  }
  
  return ans[cur];
}

int main(){
  int n;
  cin >> n;
  
  for(int i=0; i<n; i++){
    long a;
    cin >> a;
    for(long p=2; p*p<=a; p++){
      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].push_back(v);
    path[v].push_back(u);
  }
  
  for(int i=0; i<n; i++) ans[i] = mp[i];
  dfs(0);
  
  for(int i=0; i<n; i++){
    long out = 1;
    for(auto x:ans[i]){
      while(x.second--) out = out * x.first % mod;
    }
    cout << out << endl;
  }
}
0