結果
問題 |
No.3250 最小公倍数
|
ユーザー |
![]() |
提出日時 | 2025-08-30 02:42:56 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,374 bytes |
コンパイル時間 | 4,718 ms |
コンパイル使用メモリ | 253,872 KB |
実行使用メモリ | 115,840 KB |
最終ジャッジ日時 | 2025-08-30 02:43:22 |
合計ジャッジ時間 | 21,285 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | WA * 1 |
other | WA * 21 |
ソースコード
#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> prime[1000001]; 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] : prime[a[preo[i]]]) { if (mxp[id] < s) { now *= inv[mxp[id]]; now *= s; mxp[id] = s; } } } } for (auto [id, s] : prime[a[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] : prime[a[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; for (i32 i = 2; i <= 1000000; i++) { if (!prime[i].empty()) continue; i32 id = P.size(); P.push_back(i); prime[i].emplace_back(id, i); for (i32 j = i * 2; j <= 1000000; j += i) { i32 x = 1; while (j % (x * i) == 0) x *= i; prime[j].emplace_back(id, x); } } return; for (i32 i = 0; i < n; i++) { cin >> 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"; }