結果
問題 |
No.3250 最小公倍数
|
ユーザー |
![]() |
提出日時 | 2025-09-01 15:30:34 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,395 ms / 2,000 ms |
コード長 | 3,576 bytes |
コンパイル時間 | 1,020 ms |
コンパイル使用メモリ | 71,160 KB |
実行使用メモリ | 131,620 KB |
最終ジャッジ日時 | 2025-09-01 15:30:52 |
合計ジャッジ時間 | 15,465 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 21 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:138:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 138 | scanf("%d", &n); | ~~~~~^~~~~~~~~~ main.cpp:139:36: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 139 | for (int i = 0; i < n; i++) scanf("%d", as + i); | ~~~~~^~~~~~~~~~~~~~ main.cpp:142:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 142 | scanf("%d%d", &u, &v); | ~~~~~^~~~~~~~~~~~~~~~
ソースコード
/* -*- coding: utf-8 -*- * * 3250.cc: No.3250 譛蟆丞・蛟肴焚 - yukicoder */ #include<cstdio> #include<vector> #include<algorithm> #include<utility> using namespace std; /* constant */ const int MAX_N = 500000; const int MAX_P = 1000 + 50; const int MOD = 998244353; /* typedef */ using vi = vector<int>; using vb = vector<bool>; using pii = pair<int,int>; using vpii = vector<pii>; template<const int MOD> struct MI { int v; MI(): v() {} MI(int _v): v(_v % MOD) { if (v < 0) v += MOD; } MI(long long _v): v(_v % MOD) { if (v < 0) v += MOD; } explicit operator int() const { return v; } MI operator+(const MI m) const { return MI(v + m.v); } MI operator-(const MI m) const { return MI(v + MOD - m.v); } MI operator-() const { return MI(MOD - v); } MI operator*(const MI m) const { return MI((long long)v * m.v); } MI &operator+=(const MI m) { return (*this = *this + m); } MI &operator-=(const MI m) { return (*this = *this - m); } MI &operator*=(const MI m) { return (*this = *this * m); } bool operator==(const MI m) const { return v == m.v; } bool operator!=(const MI m) const { return v != m.v; } MI pow(int n) const { // a^n % MOD MI pm = 1, a = *this; while (n > 0) { if (n & 1) pm *= a; a *= a; n >>= 1; } return pm; } MI inv() const { return pow(MOD - 2); } MI operator/(const MI m) const { return *this * m.inv(); } MI &operator/=(const MI m) { return (*this = *this / m); } }; using mi = MI<MOD>; /* global variables */ vb primes; vi pnums; int as[MAX_N]; vi nbrs[MAX_N]; vpii pdss[MAX_N]; mi lcms[MAX_N]; int ps[MAX_N], cis[MAX_N]; /* subroutines */ int gen_primes(int maxp) { primes.assign(maxp + 1, true); primes[0] = primes[1] = false; int p; for (p = 2; p * p <= maxp; p++) if (primes[p]) { pnums.push_back(p); for (int q = p * p; q <= maxp; q += p) primes[q] = false; } for (; p <= maxp; p++) if (primes[p]) pnums.push_back(p); return (int)pnums.size(); } vpii prime_decomp(int n) { vpii pds; for (auto pi: pnums) { if (pi * pi > n) { if (n > 1) pds.push_back(pii(n, 1)); break; } if (n % pi == 0) { int fi = 0; while (n % pi == 0) n /= pi, fi++; pds.push_back({pi, fi}); } } return pds; } vpii mulpds(vpii &a, vpii &b) { vpii c; int an = a.size(), bn = b.size(); int i = 0, j = 0; while (i < an && j < bn) { if (a[i].first < b[j].first) c.push_back(a[i++]); else if (a[i].first > b[j].first) c.push_back(b[j++]); else { c.push_back({a[i].first, max(a[i].second, b[j].second)}); i++, j++; } } while (i < an) c.push_back(a[i++]); while (j < bn) c.push_back(b[j++]); return c; } mi pds2mi(vpii &pds) { mi x = 1; for (auto [p, d]: pds) x *= mi(p).pow(d); return x; } /* main */ int main() { gen_primes(MAX_P); int n; scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", as + i); for (int i = 1; i < n; i++) { int u, v; scanf("%d%d", &u, &v); u--, v--; nbrs[u].push_back(v); nbrs[v].push_back(u); } for (int i = 0; i < n; i++) pdss[i] = prime_decomp(as[i]); ps[0] = -1; for (int u = 0; u >= 0;) { auto &nbru = nbrs[u]; int up = ps[u]; if (cis[u] < nbru.size()) { int v = nbru[cis[u]++]; if (v != up) { ps[v] = u; u = v; } } else { lcms[u] = pds2mi(pdss[u]); if (up >= 0) pdss[up] = mulpds(pdss[up], pdss[u]); u = up; } } for (int i = 0; i < n; i++) printf("%d\n", (int)lcms[i]); return 0; }