結果
問題 |
No.3250 最小公倍数
|
ユーザー |
![]() |
提出日時 | 2025-08-29 22:44:00 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,700 ms / 2,000 ms |
コード長 | 1,833 bytes |
コンパイル時間 | 3,805 ms |
コンパイル使用メモリ | 262,112 KB |
実行使用メモリ | 135,948 KB |
最終ジャッジ日時 | 2025-08-29 22:44:23 |
合計ジャッジ時間 | 20,369 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 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]; map<i32, i32> fac[500000]; mint ans[500000]; mint dp[500000]; vector<i32> g[500000]; mint inv[2000000]; 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() { i32 mod = 998244353; inv[1] = 1; for (i32 i = 2; i < 2000000; i++) { inv[i] = -inv[mod % i] * (mod / i); } vector<bool> prime(1000001, true); vector<i32> p; prime[0] = prime[1] = false; for (i64 i = 2; i < prime.size(); i++) { if (!prime[i]) continue; p.push_back(i); for (i32 j = i * 2; j < prime.size(); j += i) prime[j] = false; } cin >> n; for (i32 i = 0; i < n; i++) { cin >> a[i]; i32 x = a[i]; for (i32 j = 0; j < p.size(); j++) { if (p[j] * p[j] > x) break; i32 c = 0, s = 1; while (x % p[j] == 0) x /= p[j], c++, s *= p[j]; if (c > 0) fac[i][p[j]] = s; } fac[i][x] = x; } 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"; } }