結果
問題 |
No.3250 最小公倍数
|
ユーザー |
![]() |
提出日時 | 2025-08-30 03:00:23 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,841 bytes |
コンパイル時間 | 4,321 ms |
コンパイル使用メモリ | 262,360 KB |
実行使用メモリ | 219,208 KB |
最終ジャッジ日時 | 2025-08-30 03:01:05 |
合計ジャッジ時間 | 36,592 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 18 TLE * 3 |
ソースコード
#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]; unordered_map<i32, i32> fac[500000]; mint ans[500000]; mint dp[500000]; vector<i32> g[500000]; mint inv[1000001]; void dfs(i32 v, i32 par) { dp[v] = a[v]; for (i64 nv : g[v]) { if (nv == par) continue; dfs(nv, v); if (fac[v].size() < fac[nv].size()) { swap(dp[v], dp[nv]); swap(fac[v], fac[nv]); } for (auto [p, s] : fac[nv]) { if (!fac[v].count(p)) { dp[v] *= s; fac[v][p] = s; } else if (fac[v][p] < s) { dp[v] *= inv[fac[v][p]]; dp[v] *= s; fac[v][p] = s; } } fac[nv].clear(); } ans[v] = dp[v]; } void _main() { cin >> n; static i32 mod = 998244353; inv[1] = 1; for (i32 i = 2; i < 1000001; i++) { inv[i] = -inv[mod % i] * (mod / i); } { vector<vector<pair<i32, i32>>> prime(1000001); vector<i32> p; for (i32 i = 2; i < prime.size(); i++) { if (!prime[i].empty()) continue; prime[i].emplace_back(i, i); p.push_back(i); for (i32 j = i * 2; j < prime.size(); j += i) { i32 s = 1; while (j % (s * i) == 0) s *= i; if (s > 1) prime[j].emplace_back(i, s); } } for (i32 i = 0; i < n; i++) { cin >> a[i]; for (auto [p, s] : prime[a[i]]) { fac[i][p] = s; } } } 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); } dfs(0, -1); for (i32 i = 0; i < n; i++) { cout << ans[i].val() << "\n"; } }