結果
問題 |
No.3250 最小公倍数
|
ユーザー |
![]() |
提出日時 | 2025-08-29 22:39:16 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,242 bytes |
コンパイル時間 | 4,722 ms |
コンパイル使用メモリ | 261,184 KB |
実行使用メモリ | 155,120 KB |
最終ジャッジ日時 | 2025-08-29 22:39:45 |
合計ジャッジ時間 | 23,805 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
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(); } i64 n; i64 a[500000]; map<i64, p2> fac[500000]; mint ans[500000]; mint dp[500000]; vector<i64> g[500000]; void dfs(i64 v, i64 par) { dp[v] = a[v]; for (i64 nv : g[v]) { if (nv == par) continue; dfs(nv, v); if (fac[v].size() > fac[nv].size()) { for (auto [p, cs] : fac[nv]) { auto [c, s] = cs; if (!fac[v].count(p)) { dp[v] *= s; fac[v][p] = {c, s}; } else if (fac[v][p].first < c) { dp[v] /= fac[v][p].second; dp[v] *= s; fac[v][p] = {c, s}; } } fac[nv].clear(); } else { swap(dp[v], dp[nv]); swap(fac[v], fac[nv]); for (auto [p, cs] : fac[nv]) { auto [c, s] = cs; if (!fac[v].count(p)) { dp[v] *= s; fac[v][p] = {c, s}; } else if (fac[v][p].first < c) { dp[v] /= fac[v][p].second; dp[v] *= s; fac[v][p] = {c, s}; } } fac[nv].clear(); } } ans[v] = dp[v]; } void _main() { vector<bool> prime(1000001, true); vector<i64> p; prime[0] = prime[1] = false; for (i64 i = 2; i < prime.size(); i++) { if (!prime[i]) continue; p.push_back(i); for (i64 j = i * 2; j < prime.size(); j += i) prime[j] = false; } cin >> n; for (i64 i = 0; i < n; i++) { cin >> a[i]; i64 x = a[i]; for (i64 j = 0; j < p.size(); j++) { if (p[j] * p[j] > x) break; i64 c = 0, s = 1; while (x % p[j] == 0) x /= p[j], c++, s *= p[j]; // if (c > 0) fac[i].push_back({j, c}); if (c > 0) fac[i][p[j]] = {c, s}; } i64 j = lower_bound(p.begin(), p.end(), x) - p.begin(); // fac[i].push_back({j, 1}); fac[i][x] = {1, x}; } for (i64 i = 0; i < n - 1; i++) { i64 u, v; cin >> u >> v; u--, v--; g[u].push_back(v); g[v].push_back(u); } dfs(0, -1); for (i64 i = 0; i < n; i++) { cout << ans[i].val() << "\n"; } }