結果
問題 |
No.3250 最小公倍数
|
ユーザー |
|
提出日時 | 2025-08-30 01:43:27 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,918 ms / 2,000 ms |
コード長 | 7,056 bytes |
コンパイル時間 | 2,337 ms |
コンパイル使用メモリ | 208,704 KB |
実行使用メモリ | 41,156 KB |
最終ジャッジ日時 | 2025-08-30 01:43:48 |
合計ジャッジ時間 | 19,777 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 21 |
ソースコード
#include <bits/stdc++.h> #include <variant> #define rep2(i, k, n) for (i64 i = (i64)(k); i < (i64)(n); i++) #define rep(i, n) rep2(i, 0, n) #define all(x) begin(x), end(x) #ifdef ENV_LOCAL #define dump \ if (1) cerr #else #define dump \ if (0) cerr #endif using namespace std; using namespace std::string_literals; using i32 = int32_t; using i64 = int64_t; using f64 = double; using f80 = long double; using vi32 = vector<i32>; using vi64 = vector<i64>; /* * harudake::modint * * Copyright (c) 2021 prime number * * This software is released under the MIT license. * see https://opensource.org/licenses/MIT * */ namespace harudake { template <typename base_t, base_t MOD> class static_modint; using modint_1000000007 = static_modint<uint64_t, 1'000'000'007>; using modint_998244353 = static_modint<uint64_t, 998'244'353>; template <typename base_t, base_t MOD> static_modint<base_t, MOD> add(const static_modint<base_t, MOD> lhs, const static_modint<base_t, MOD> rhs) { base_t tmp = lhs.val + rhs.val; if (tmp >= MOD) tmp -= MOD; return static_modint<base_t, MOD>::make_raw(tmp); } template <typename base_t, base_t MOD> static_modint<base_t, MOD> sub(const static_modint<base_t, MOD> lhs, const static_modint<base_t, MOD> rhs) { base_t tmp = lhs.val + MOD - rhs.val; if (tmp >= MOD) tmp -= MOD; return static_modint<base_t, MOD>::make_raw(tmp); } template <typename base_t, base_t MOD> static_modint<base_t, MOD> mul(const static_modint<base_t, MOD> lhs, const static_modint<base_t, MOD> rhs) { base_t tmp = lhs.val * rhs.val; tmp %= MOD; return static_modint<base_t, MOD>::make_raw(tmp); } // data types must be signed integer inline int64_t inv(const int64_t a, const int64_t p) { return (a == 1 ? 1 : (1 - p * inv(p % a, a)) / a + p); }; template <typename base_t, base_t MOD> static_modint<base_t, MOD> div(const static_modint<base_t, MOD> lhs, const static_modint<base_t, MOD> rhs) { base_t tmp = lhs.val * inv(rhs.val, MOD); tmp %= MOD; return static_modint<base_t, MOD>::make_raw(tmp); } template <typename base_t, base_t MOD> static_modint<base_t, MOD> pow(const static_modint<base_t, MOD> base, const uint64_t index) { if (index == 0) return static_modint<base_t, MOD>{1}; if (index % 2 == 1) { return pow(base, index - 1) * base; } else { auto half = pow(base, index / 2); return half * half; } } template <typename base_t, base_t MOD> class static_modint { using modint = static_modint; public: static constexpr base_t mod = MOD; static_modint() : val(0) {} static_modint(const base_t x) : val(x % MOD) {} static_modint(const modint&) = default; modint& operator=(const modint&) = default; modint& operator=(const base_t x) { val = x % MOD; return *this; } modint operator-() const { return val == 0 ? 0 : MOD - val; } explicit operator base_t() const { return val; } base_t get() const { return val; } constexpr base_t get_mod() const { return mod; } static modint make_raw(const base_t raw) { modint res; res.val = raw; return res; } private: friend modint add<base_t, MOD>(const modint, const modint); friend modint sub<base_t, MOD>(const modint, const modint); friend modint mul<base_t, MOD>(const modint, const modint); friend modint div<base_t, MOD>(const modint, const modint); base_t val; }; template <typename base_t, base_t MOD> static_modint<base_t, MOD> operator+(const static_modint<base_t, MOD> lhs, const static_modint<base_t, MOD> rhs) { return add(lhs, rhs); } template <typename base_t, base_t MOD> static_modint<base_t, MOD> operator-(const static_modint<base_t, MOD> lhs, const static_modint<base_t, MOD> rhs) { return sub(lhs, rhs); } template <typename base_t, base_t MOD> static_modint<base_t, MOD> operator*(const static_modint<base_t, MOD> lhs, const static_modint<base_t, MOD> rhs) { return mul(lhs, rhs); } template <typename base_t, base_t MOD> static_modint<base_t, MOD> operator/(const static_modint<base_t, MOD> lhs, const static_modint<base_t, MOD> rhs) { return div(lhs, rhs); } template <typename base_t, base_t MOD> static_modint<base_t, MOD> operator^(const static_modint<base_t, MOD> lhs, const uint64_t rhs) { return pow(lhs, rhs); } template <typename base_t, base_t MOD> static_modint<base_t, MOD>& operator+=(static_modint<base_t, MOD>& lhs, const static_modint<base_t, MOD> rhs) { return lhs = lhs + rhs; } template <typename base_t, base_t MOD> static_modint<base_t, MOD>& operator-=(static_modint<base_t, MOD>& lhs, const static_modint<base_t, MOD> rhs) { return lhs = lhs - rhs; } template <typename base_t, base_t MOD> static_modint<base_t, MOD>& operator*=(static_modint<base_t, MOD>& lhs, const static_modint<base_t, MOD> rhs) { return lhs = lhs * rhs; } template <typename base_t, base_t MOD> static_modint<base_t, MOD>& operator/=(static_modint<base_t, MOD>& lhs, const static_modint<base_t, MOD> rhs) { return lhs = lhs / rhs; } template <typename base_t, base_t MOD> static_modint<base_t, MOD>& operator^=(static_modint<base_t, MOD>& lhs, const uint64_t rhs) { return lhs = lhs ^ rhs; } } // namespace harudake using namespace harudake; using mint = modint_998244353; struct dp_data { map<i32, i32> factors; mint prod; }; map<i32, i32> factorize(i32 x) { map<i32, i32> res; for (i32 i = 2; i * i <= x; i++) { while (x % i == 0) { res[i]++; x /= i; } } if (x > 1) res[x]++; return res; } dp_data to_dp_data(i32 x) { dp_data res; res.prod = 1; for (auto [p, e] : factorize(x)) { res.factors[p] = e; res.prod *= mint(p) ^ e; } return res; } void merge_dp_data(dp_data& a, dp_data& b) { if (a.factors.size() < b.factors.size()) swap(a, b); for (auto [p, e] : b.factors) { if (a.factors[p] < e) { a.prod *= mint(p) ^ (e - a.factors[p]); a.factors[p] = e; } } } dp_data dfs(i32 v, i32 p, const vector<vi32>& t, const vi32& a, vector<mint>& ans) { dp_data res = to_dp_data(a[v]); for (i32 u : t[v]) { if (u == p) continue; auto sub = dfs(u, v, t, a, ans); merge_dp_data(res, sub); } ans[v] = res.prod; return res; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); i32 n; cin >> n; vi32 a(n); rep(i, n) cin >> a[i]; vector<vi32> t(n); rep(i, n - 1) { i32 u, v; cin >> u >> v; u--; v--; t[u].push_back(v); t[v].push_back(u); } vector<mint> ans(n); dfs(0, -1, t, a, ans); rep(i, n) { cout << ans[i].get() << "\n"; } return 0; }