結果

問題 No.3250 最小公倍数
ユーザー areik
提出日時 2025-08-30 02:47:18
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,600 bytes
コンパイル時間 4,556 ms
コンパイル使用メモリ 254,908 KB
実行使用メモリ 319,304 KB
最終ジャッジ日時 2025-08-30 02:47:44
合計ジャッジ時間 25,540 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18 TLE * 1 -- * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

using i32 = int;
using i64 = long long;
using f64 = double;
using p2 = pair<i64, i64>;
using el = tuple<i64, i64, i64>;
using mint = atcoder::modint998244353;

void _main();
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  _main();
}

i32 n;
i32 a[500000];
i32 siz[500000];
i32 idx[500000], jdx[500000];
mint inv[1000001];
vector<i32> preo;
vector<i32> g[500000];
vector<i32> P;
vector<p2> fac[500000];
void dfs1(i32 v, i32 par) {
  siz[v] = 1;
  idx[v] = jdx[v] = preo.size();
  preo.push_back(v);
  for (i32 nv : g[v]) {
    if (nv != par) {
      dfs1(nv, v);
      siz[v] += siz[nv];
      jdx[v] = jdx[nv];
    }
  }
}
vector<i32> mxp;
mint now;
mint ans[500000];
void dfs2(i32 v, i32 par, bool keep) {
  i32 mxc = -1, vh = -1;
  for (i32 nv : g[v]) if (nv != par && mxc < siz[nv]) mxc = siz[nv], vh = nv; 
  for (i32 nv : g[v]) if (nv != par && nv != vh) {
    dfs2(nv, v, false);
  }
  if (vh != -1) dfs2(vh, v, true);
  else now = 1;
  for (i32 nv : g[v]) if (nv != par && nv != vh) {
    for (i32 i = idx[nv]; i <= jdx[nv]; i++) {
      for (auto [id, s] : fac[preo[i]]) {
        if (mxp[id] < s) {
          now *= inv[mxp[id]];
          now *= s;
          mxp[id] = s;
        }
      }
    }
  }
  for (auto [id, s] : fac[v]) {
    if (mxp[id] < s) {
      now *= inv[mxp[id]];
      now *= s;
      mxp[id] = s;
    }
  }
  ans[v] = now;
  if (keep) return;
  for (i32 i = idx[v]; i <= jdx[v]; i++) {
    for (auto [id, s] : fac[preo[i]]) {
      mxp[id] = 1;
    }
  }
  now = 1;
}
void _main() {
  static i32 mod = 998244353;
  inv[1] = 1;
  for (i32 i = 2; i <= 1000000; i++) inv[i] = -inv[mod % i] * (mod / i);
  cin >> n;
  vector<bool> prime(1000001, true);
  for (i32 i = 2; i <= 1000000; i++) {
    if (!prime[i]) continue;
    i32 id = P.size();
    P.push_back(i);
    for (i32 j = i * 2; j <= 1000000; j += i) {
      prime[j] = false;
    }
  }
  for (i32 i = 0; i < n; i++) {
    cin >> a[i];
    for (i32 j = 0; j < P.size(); j++) {
      if (P[j] * P[j] > a[i]) break;
      i32 c = 1;
      while (a[i] % P[j] == 0) a[i] /= P[j], c *= P[j];
      if (c > 0) fac[i].emplace_back(j, c);
    }
    if (a[i] == 1) continue;
    i32 j = lower_bound(P.begin(), P.end(), a[i]) - P.begin();
    fac[i].emplace_back(j, a[i]);
  }
  for (i32 i = 0; i < n - 1; i++) {
    i32 u, v;
    cin >> u >> v;
    u--, v--;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  mxp = vector<i32>(P.size(), 1);
  dfs1(0, -1);
  dfs2(0, -1, false);
  for (i32 i = 0; i < n; i++) cout << ans[i].val() << "\n";
}
0