結果
| 問題 |
No.3250 最小公倍数
|
| ユーザー |
 dp_ijk
|
| 提出日時 | 2025-08-29 23:03:51 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,794 ms / 2,000 ms |
| コード長 | 18,943 bytes |
| コンパイル時間 | 3,136 ms |
| コンパイル使用メモリ | 214,300 KB |
| 実行使用メモリ | 181,048 KB |
| 最終ジャッジ日時 | 2025-08-29 23:04:21 |
| 合計ジャッジ時間 | 17,910 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 21 |
ソースコード
#define NDEBUG
#pragma GCC optimize("Ofast")
#include <algorithm>
#include <array>
#include <bit>
#include <cassert>
#include <cmath>
#include <cstddef>
#include <cstdint>
#include <cstdlib>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <random>
#include <ranges>
#include <set>
#include <sstream>
#include <stdexcept>
#include <string>
#include <tuple>
#include <type_traits>
#include <utility>
#include <vector>
struct IOSetup {
IOSetup() {
std::cin.tie(nullptr);
std::ios::sync_with_stdio(false);
std::cout << std::fixed << std::setprecision(15);
std::cerr << std::fixed << std::setprecision(8);
}
};
IOSetup iosetup;
using ll = int64_t;
using int128_t = __int128;
using uint128_t = unsigned __int128;
template <typename T>
constexpr auto rep_iota_impl(T start, T stop) noexcept {
return std::views::iota(start, (start < stop ? stop : start));
}
template <typename T = int64_t>
inline constexpr auto rep_impl(auto start, auto stop) noexcept {
return rep_iota_impl<T>(start, stop);
}
template <typename T = int64_t>
inline constexpr auto rep_impl(auto stop) noexcept {
return rep_iota_impl<T>(0, stop);
}
template <class... Ts>
inline void read(Ts&... ts) {
(std::cin >> ... >> ts);
}
template <typename T = int64_t>
std::vector<T> VEC(int size) {
std::vector<T> res(size);
for (T& x : res)
std::cin >> x;
return res;
}
template <class Iterable>
auto max(const Iterable& A) {
if (A.empty()) { assert(false); }
return *std::max_element(A.begin(), A.end());
}
template <typename T, typename T2>
auto max(T a, T2 b) -> std::common_type_t<T, T2> {
return (a < b) ? b : a;
}
using std::vector;
template <typename T>
void cumsum_inplace(vector<T>& A) {
for (const auto i : rep_impl(A.size() - 1))
A[i + 1] = A[i] + A[i + 1];
}
template <typename T>
vector<T> cumsum(vector<T> A, auto initial) {
A.insert(A.begin(), static_cast<T>(initial));
cumsum_inplace(A);
return A;
}
template <typename T = int64_t>
inline constexpr std::pair<T, T> inv_gcd(T a, T base) {
static_assert(std::is_signed<T>::value);
assert(base != 0);
if (base < 0) base = -(base);
if ((a %= base) < 0) a += base;
if (a == 0) return {base, 0};
T s = base, t = a;
T m0 = 0, m1 = 1;
while (t) {
const T u = s / t;
s -= t * u;
m0 -= m1 * u;
std::swap(s, t);
std::swap(m0, m1);
}
if (m0 < 0) m0 += base / s;
return {s, m0};
}
template <typename T, typename UInt>
inline constexpr UInt safe_mod_uint(const T x, const UInt d) {
static_assert(std::is_integral_v<T>);
static_assert(std::is_integral_v<UInt> && std::is_unsigned_v<UInt>);
assert(d != 0);
if constexpr (std::is_signed_v<T>) {
if (x >= 0) {
return static_cast<UInt>(x % d);
} else {
using T2 = std::make_unsigned_t<T>;
T2 abs = T2(0) - static_cast<T2>(x);
abs %= d;
return (abs != 0) ? static_cast<UInt>(d - abs) : 0;
}
} else if constexpr (std::is_unsigned_v<T>) {
return static_cast<UInt>(x % d);
} else {
static_assert([]() -> bool { return false; }());
}
}
template <typename U1, typename U2>
inline constexpr U1 pow_mod_constexpr(U1 base, auto exp, const U1 mod) {
assert(mod != 0);
assert(0 <= exp);
if (mod == 1) return 0;
if (not(base < mod)) base %= mod;
assert(0 <= base && base < mod);
U1 res = 1;
while (exp) {
if (exp & 1) res = static_cast<U2>(res) * base % mod;
base = static_cast<U2>(base) * base % mod;
exp >>= 1;
}
return res;
}
inline constexpr uint32_t pow_mod_uint32(auto base, int64_t exp, uint32_t mod) {
assert(0 <= exp);
assert(mod != 0);
return pow_mod_constexpr<uint32_t, uint64_t>(safe_mod_uint(base, mod), exp, mod);
}
inline uint64_t pow_mod_uint64(auto base, int64_t exp, uint64_t mod) {
using uint128_t = unsigned __int128;
assert(0 <= exp);
assert(mod != 0);
return pow_mod_constexpr<uint64_t, uint128_t>(safe_mod_uint(base, mod), exp, mod);
}
template <typename T>
void put(const T& t) {
std::cout << t;
}
template <typename... Ts>
void print(const Ts&... ts) {
put(ts...);
std::cout << "\n";
}
using std::cin;
using std::cout;
using std::map;
using std::pair;
using std::set;
using std::string;
using std::tuple;
using std::vector;
inline pair<vector<int64_t>, vector<int64_t>> lpf_table(int64_t N) {
using ll = int64_t;
if (N <= 1) { N = 1; }
vector<ll> dp(N + 1, 0);
vector<ll> P;
for (const auto x : rep_impl(2, N + 1)) {
if (dp[x] == 0) {
dp[x] = x;
P.push_back(x);
}
const ll lpf = dp[x];
for (ll np : P) {
if (lpf < np || !(np * x <= N)) { break; }
dp[np * x] = np;
}
}
return {dp, P};
}
using ll = int64_t;
inline pair<vector<ll>, vector<ll>> lpf_exp_pow(const vector<ll>& lpf) {
if (lpf.size() <= 1) return {vector<ll>{0, 0}, vector<ll>{0, 0}};
const ll N = lpf.size() - 1;
vector<ll> exp(N + 1, 1);
vector<ll> pow(lpf);
exp[0] = exp[1] = 0;
pow[0] = pow[1] = 0;
for (const auto x : rep_impl(2, N + 1)) {
const ll p = lpf[x];
const ll y = x / p;
if (y % p == 0) {
exp[x] = exp[y] + 1;
pow[x] = pow[y] * p;
}
}
return {exp, pow};
}
using std::pair;
using std::vector;
struct LinearSieve {
using ll = int64_t;
ll N;
vector<ll> _lpf, P;
vector<ll> lpf_exp, lpf_pow;
public:
explicit LinearSieve(ll N_) {
N = max(0, N_) + 1000;
std::tie(_lpf, P) = lpf_table(N);
std::tie(lpf_exp, lpf_pow) = lpf_exp_pow(_lpf);
}
ll lpf(ll X) const {
assert(1 <= X && X <= N);
return _lpf[X];
}
vector<pair<ll, ll>> factors(ll X) const {
assert(1 <= X && X <= N);
vector<pair<ll, ll>> F;
while (2 <= X) {
ll p = lpf(X);
ll e = lpf_exp[X];
ll pow = lpf_pow[X];
X /= pow;
F.push_back({p, e});
}
return F;
}
};
using std::pair;
using std::vector;
template <typename T>
struct CSR {
using ll = int64_t;
ll N = 0;
vector<ll> start{};
vector<ll> I;
vector<T> E;
bool frozen = false;
CSR() = default;
explicit CSR(ll N)
: N(N),
start(N + 1) {}
explicit CSR(ll N, vector<pair<ll, T>> IE)
: N(N) {
for (auto [i, t] : IE) {
I.push_back(i);
E.push_back(t);
}
build();
}
void reset(ll N) {
this->N = N;
start.resize(N + 1);
I.clear();
E.clear();
frozen = false;
}
void clear() { reset(0); }
void push_back(ll i, T t) {
assert(!frozen);
assert(0 <= i && i < N);
I.push_back(i);
E.push_back(t);
}
void build() {
assert(!frozen);
const ll M = E.size();
vector<ll> C(N);
vector<T> nE(M);
for (const auto j : rep_impl(M)) {
assert(0 <= I[j] && I[j] < N);
C[I[j]] += 1;
}
start = cumsum(C, 0);
auto it = start;
for (const auto j : rep_impl(M)) {
ll i = I[j];
nE[it[i]] = E[j];
it[i] += 1;
}
std::swap(E, nE);
I.clear();
frozen = true;
}
auto operator[](int64_t idx) const {
assert(frozen);
assert(0 <= idx && idx < N);
return std::ranges::subrange(E.begin() + start[idx], E.begin() + start[idx + 1]);
}
auto operator[](int64_t idx) {
assert(frozen);
assert(0 <= idx && idx < N);
return std::ranges::subrange(E.begin() + start[idx], E.begin() + start[idx + 1]);
}
using subrange = std::ranges::subrange<typename vector<T>::iterator>;
subrange at(int64_t idx) {
assert(frozen);
assert(0 <= idx && idx < N);
return std::ranges::subrange(E.begin() + start[idx], E.begin() + start[idx + 1]);
}
ll size() const { return N; }
ll num_edges() const { return E.size(); }
template <typename U>
static CSR<U> from_vector(const vector<vector<U>>& G) {
CSR<U> res;
res.N = G.size();
for (const auto i : rep_impl(res.N)) {
for (auto e : G[i]) {
res.push_back(i, e);
}
}
res.build();
return res;
}
vector<vector<T>> to_vector() const {
vector<vector<T>> res(N);
for (const auto i : rep_impl(N)) {
for (auto e : at(i)) {
res[i].push_back(e);
}
}
return res;
}
};
template <bool weighted = false, typename Weight = int64_t>
struct Tree {
using ll = int64_t;
constexpr static ll NIL = -1e9;
ll N = NIL;
ll M = 0;
ll root = NIL;
CSR<pair<ll, Weight>> G_weighted;
CSR<pair<ll, Weight>> T_weighted;
CSR<ll> T;
vector<ll> pi;
vector<Weight> pi_edge_cost;
vector<ll> depth;
vector<Weight> depth_weighted;
vector<ll> root_to_leaf;
vector<ll> subtree_size;
vector<ll> called_at;
vector<ll> index;
vector<ll> edge_tour;
vector<ll> head;
bool frozen = false;
private:
void resize_fields(ll N) {
pi.assign(N, NIL);
pi_edge_cost.assign(N, Weight{});
depth.assign(N, NIL);
depth_weighted.assign(N, NIL);
root_to_leaf.clear();
root_to_leaf.reserve(N);
subtree_size.assign(N, 1);
called_at.assign(N, NIL);
index.assign(N, NIL);
edge_tour.clear();
edge_tour.reserve(2 * N);
head.assign(N, NIL);
}
public:
Tree(ll N, ll root = NIL)
: N(N),
M(0),
root(root),
G_weighted(N) {
if (N == 1) {
root = 0;
build();
}
}
void add_undirected_edge(ll frm, ll to) {
static_assert(not weighted);
add_undirected_edge(frm, to, Weight{1});
}
void add_undirected_edge(ll frm, ll to, Weight cost) {
assert(!frozen);
G_weighted.push_back(frm, {to, cost});
G_weighted.push_back(to, {frm, cost});
M += 1;
if (0 < N && M == N - 1 && 0 <= root && root < N) { build(); }
}
void reset(ll N) {
this->N = N;
M = 0;
root = NIL;
frozen = false;
}
void build() {
if (frozen) return;
assert(!frozen);
assert(N != NIL);
assert(N != 0 && M == N - 1);
assert(0 <= root && root < N);
assert(G_weighted.size() == N);
G_weighted.build();
T_weighted.reset(N);
T.reset(N);
resize_fields(N);
depth[root] = 0;
dfs(root, NIL);
T_weighted.build();
T.build();
head[root] = root;
hld(root, NIL);
G_weighted.clear();
frozen = true;
}
void dfs(ll v, ll p) {
for (auto [a, cost] : G_weighted[v]) {
if (a == p) continue;
T_weighted.push_back(v, {a, cost});
T.push_back(v, a);
depth[a] = depth[v] + 1;
depth_weighted[a] = depth_weighted[v] + cost;
pi[a] = v;
pi_edge_cost[a] = cost;
dfs(a, v);
subtree_size[v] += subtree_size[a];
}
}
auto iter_subtree(ll v) {
ll start = index[v];
ll end = start + subtree_size[v];
return std::ranges::subrange(root_to_leaf.begin() + start, root_to_leaf.begin() + end);
}
void hld(ll v, ll p) {
index[v] = root_to_leaf.size();
called_at[v] = edge_tour.size();
edge_tour.push_back(v);
root_to_leaf.push_back(v);
ll maxsize = 0;
ll eldest = NIL;
ll argmax = NIL;
for (const auto j : rep_impl(T[v].size())) {
ll a = T[v][j];
assert(a != p);
if (maxsize < subtree_size[a]) {
maxsize = subtree_size[a];
eldest = a;
argmax = j;
}
}
if (eldest != NIL) {
std::swap(T_weighted.at(v)[0], T_weighted.at(v)[argmax]);
std::swap(T.at(v)[0], T.at(v)[argmax]);
head[eldest] = head[v];
hld(eldest, v);
}
for (const auto i : rep_impl(1, T[v].size())) {
auto a = T[v][i];
head[a] = a;
hld(a, v);
}
edge_tour.push_back(~v);
}
auto operator[](ll v) {
if constexpr (weighted) { return T_weighted[v]; }
return T[v];
}
auto adj(ll v) { return T[v]; }
ll size() const { return N; }
};
constexpr int64_t MOD = 998'244'353;
constexpr bool is_prime32_constexpr(uint32_t n) {
if (n <= 1) return false;
if (n == 2 || n == 7 || n == 61) return true;
if (n % 2 == 0) return false;
uint32_t d = n - 1;
while (d % 2 == 0)
d /= 2;
constexpr uint32_t bases[3] = {2, 7, 61};
for (uint32_t a : bases) {
uint32_t t = d;
uint32_t y = pow_mod_constexpr<uint32_t, uint64_t>(a, t, n);
while (t != n - 1 && y != 1 && y != n - 1) {
y = y * y % n;
t <<= 1;
}
if (y != n - 1 && t % 2 == 0) { return false; }
}
return true;
}
static_assert(is_prime32_constexpr(2));
template <int64_t MOD_>
struct static_modint {
static_assert(1 <= MOD_);
static_assert(MOD_ < (uint32_t{1} << 31));
static constexpr int32_t MOD = int32_t{MOD_};
static constexpr uint32_t UMOD = uint32_t{MOD};
static_assert(std::in_range<int32_t>(MOD_));
static_assert(std::in_range<int32_t>(MOD));
static_assert(std::in_range<int32_t>(UMOD));
using mint = static_modint;
uint32_t _v = 0;
private:
static constexpr bool is_prime = is_prime32_constexpr(UMOD);
static constexpr uint32_t inv_uint32(uint32_t x) {
assert(x != 0);
if constexpr (is_prime) {
return pow_mod_uint32(x, UMOD - 2, UMOD);
} else {
auto [g, inv] = inv_gcd<int32_t>(x, UMOD);
assert(g == 1);
return inv;
}
}
public:
static constexpr mint raw(uint32_t v) noexcept {
mint a;
a._v = v;
return a;
}
constexpr static_modint()
: _v(0) {}
constexpr static_modint(int32_t v)
: _v((v %= MOD) < 0 ? v + MOD : v) {}
constexpr static_modint(int64_t v)
: _v((v %= MOD) < 0 ? v + MOD : v) {}
constexpr static_modint(uint32_t v)
: _v(v % UMOD) {}
constexpr static_modint(uint64_t v)
: _v(v % UMOD) {}
static constexpr int32_t mod() { return MOD; }
static constexpr int32_t get_mod() { return mod(); }
constexpr int32_t val() const { return _v; }
constexpr mint& operator+=(mint rhs) {
if (_v >= UMOD - rhs._v) _v -= UMOD;
_v += rhs._v;
return *this;
}
constexpr mint& operator-=(mint rhs) {
if (_v < rhs._v) _v += UMOD;
_v -= rhs._v;
return *this;
}
constexpr mint& operator*=(mint rhs) {
_v = (uint64_t)_v * rhs._v % UMOD;
return *this;
}
constexpr mint& operator/=(mint rhs) {
_v = (uint64_t)_v * inv_uint32(rhs._v) % UMOD;
return *this;
}
constexpr mint operator+() const { return *this; }
constexpr mint operator-() const {
if (_v == 0) return *this;
return mint::raw(UMOD - _v);
}
friend constexpr mint operator+(mint lhs, mint rhs) { return lhs += rhs; }
friend constexpr mint operator-(mint lhs, mint rhs) { return lhs -= rhs; }
friend constexpr mint operator*(mint lhs, mint rhs) { return lhs *= rhs; }
friend constexpr mint operator/(mint lhs, mint rhs) { return lhs /= rhs; }
friend constexpr bool operator<(mint lhs, mint rhs) { return lhs._v < rhs._v; }
friend constexpr bool operator==(mint lhs, mint rhs) { return lhs._v == rhs._v; }
friend constexpr bool operator!=(mint lhs, mint rhs) { return lhs._v != rhs._v; }
constexpr mint inv() const {
assert(_v != 0);
return mint::raw(inv_uint32(_v));
}
constexpr mint pow(const int64_t exp) const {
if (exp < 0) { return mint::raw(pow_mod_uint32(inv_uint32(_v), -exp, UMOD)); }
return mint::raw(pow_mod_uint32(_v, exp, UMOD));
}
struct ntt_info_t {
int rank2;
int omega;
};
static constexpr ntt_info_t ntt_info() {
if (UMOD == 167772161) return {25, 17};
if (UMOD == 469762049) return {26, 30};
if (UMOD == 754974721) return {24, 362};
if (UMOD == 998244353) return {23, 31};
return {-1, -1};
}
static constexpr bool ntt_friendly = (ntt_info().rank2 != -1);
friend std::ostream& operator<<(std::ostream& os, const mint& x) { return os << x.val(); }
friend std::istream& operator>>(std::istream& is, mint& x) {
int64_t v;
is >> v;
x = mint(v);
return is;
}
};
using mint = static_modint<MOD>;
int main() {
int64_t N;
read(N);
auto A = VEC(N);
ll U = max(A);
vector<pair<ll, ll>> E;
auto T = Tree<0>(N, 0);
for ([[maybe_unused]] const auto _i : rep_impl(N - 1)) {
int64_t a, b;
read(a, b);
a -= 1, b -= 1;
T.add_undirected_edge(a, b);
}
T.build();
vector<ll> res(N);
vector<ll> C(U + 1, 0);
vector<ll> ord(U + 1, 0);
vector<ll> used;
auto ls = LinearSieve(U);
mint lcm = 1;
auto push = [&](ll x) {
if (C[x] == 0) {
for (auto [p, e] : ls.factors(x)) {
if (ord[p] == 0) { used.push_back(p); }
if (ord[p] < e) {
lcm *= mint(p).pow(e - ord[p]);
ord[p] = e;
}
}
}
C[x] += 1;
};
auto del = [&](ll x) { C[x] -= 1; };
auto dfs = [&](auto&& dfs, ll x, bool keep) -> void {
ll eldest = -1;
if (T[x].size()) { eldest = T[x][0]; }
for (auto a : T[x]) {
if (a != eldest) { dfs(dfs, a, 0); }
}
if (eldest != -1) { dfs(dfs, eldest, 1); }
for (auto a : T[x]) {
if (a != eldest) {
for (auto b : T.iter_subtree(a)) {
push(A[b]);
}
}
}
push(A[x]);
res[x] = lcm.val();
if (!keep) {
for (auto a : T.iter_subtree(x)) {
del(A[a]);
}
for (auto p : used) {
ord[p] = 0;
}
used.clear();
lcm = 1;
}
return;
};
dfs(dfs, 0, 1);
for (auto a : res) {
print(a);
}
}