結果
| 問題 |
No.3250 最小公倍数
|
| ユーザー |
 kwm_t
|
| 提出日時 | 2025-08-30 15:13:12 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,140 ms / 2,000 ms |
| コード長 | 10,181 bytes |
| コンパイル時間 | 6,650 ms |
| コンパイル使用メモリ | 332,976 KB |
| 実行使用メモリ | 226,460 KB |
| 最終ジャッジ日時 | 2025-08-30 15:13:34 |
| 合計ジャッジ時間 | 17,444 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 21 |
ソースコード
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
// using mint = modint1000000007;
// const int mod = 1000000007;
using mint = modint998244353;
const int mod = 998244353;
// const int INF = 1e9;
// const long long LINF = 1e18;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep2(i, l, r) for (int i = (l); i < (r); ++i)
#define rrep(i, n) for (int i = (n) - 1; i >= 0; --i)
#define rrep2(i, l, r) for (int i = (r) - 1; i >= (l); --i)
#define all(x) (x).begin(), (x).end()
#define allR(x) (x).rbegin(), (x).rend()
#define P pair<int, int>
template <typename A, typename B>
inline bool chmax(A& a, const B& b) {
if (a < b) {
a = b;
return true;
}
return false;
}
template <typename A, typename B>
inline bool chmin(A& a, const B& b) {
if (a > b) {
a = b;
return true;
}
return false;
}
#include <algorithm>
#include <vector>
class Tree {
public:
Tree(int n, int root) : n(n), root(root) {
edge.resize(n);
for (int i = 0; i < MAXLOGV; i++)
parent[i].resize(n);
depth.resize(n);
}
// uとvをつなぐ
// lcaを求めることが主目的なので無向グラフとしている
void unite(int u, int v) {
edge[u].push_back(v);
edge[v].push_back(u);
}
// initする
// コンストラクタだけじゃなくてこれも呼ばないとlcaが求められないぞ
void init() {
dfsOrder.resize(n);
dfs(root, -1, 0);
for (int k = 0; k + 1 < MAXLOGV; k++) {
for (int v = 0; v < n; v++) {
if (parent[k][v] < 0)
parent[k + 1][v] = -1;
else
parent[k + 1][v] = parent[k][parent[k][v]];
}
}
}
// uとvのlcaを求める
int lca(int u, int v) const {
if (depth[u] > depth[v])
std::swap(u, v);
for (int k = 0; k < MAXLOGV; k++) {
if ((depth[v] - depth[u]) >> k & 1) {
v = parent[k][v];
}
}
if (u == v)
return u;
for (int k = MAXLOGV - 1; k >= 0; k--) {
if (parent[k][u] != parent[k][v]) {
u = parent[k][u];
v = parent[k][v];
}
}
return parent[0][u];
}
// uのn個親を求める
int pare(int v, int n) {
if (depth[v] < n)
return -1;
n = std::min(n, depth[v]);
int idx = MAXLOGV;
while (n) {
for (int i = idx - 1; i >= 0; --i) {
if (n < (1 << i))
continue;
if (-1 == parent[i][v])
continue;
n -= (1 << i);
v = parent[i][v];
idx = i;
break;
}
}
return v;
}
// uからvに向かってd進んだ頂点を返す
int JumpOnTree(int u, int v, int d) {
if (0 == d)
return u;
int distuv = dist(u, v);
if (distuv < d)
return -1;
int l = lca(u, v);
if (l == u)
return pare(v, distuv - d);
if (l == v)
return pare(u, d);
int distlu = dist(l, u);
if (distlu >= d)
return pare(u, d);
return pare(v, distuv - d);
}
// uとvの距離を求める
// edgeを定義しないといけない時はこれじゃダメ
int dist(int u, int v) const {
int p = lca(u, v);
return (depth[u] - depth[p]) + (depth[v] - depth[p]);
}
// 頂点wが頂点u,vのパス上に存在するか
bool on_path(int u, int v, int w) {
return (dist(u, w) + dist(v, w) == dist(u, v));
}
int tmp = 0;
int dfs(int v, int p, int d) {
dfsOrder[v] = tmp;
tmp++;
int ret = 1;
parent[0][v] = p;
depth[v] = d;
for (int next : edge[v]) {
if (next == p)
continue;
auto get = dfs(next, v, d + 1);
ret += get;
}
return ret;
}
static const int MAXLOGV = 25;
// グラフの隣接リスト表現
std::vector<std::vector<int>> edge;
// 頂点の数
int n;
// 根ノードの番号
int root;
// 親ノード
std::vector<int> parent[MAXLOGV];
// 根からの深さ
std::vector<int> depth;
// dfsorder
std::vector<int> dfsOrder;
};
class Osa_k {
public:
Osa_k(int max = 1000006) { osa_k.resize(max + 1); }
void init() {
osa_k[1] = 1;
for (int i = 2; i < osa_k.size(); ++i) {
if (0 != osa_k[i])
continue;
osa_k[i] = i;
for (int j = i * 2; j < osa_k.size(); j += i) {
if (0 == osa_k[j])
osa_k[j] = i;
}
}
}
std::vector<int> osk(int n) {
std::vector<int> result;
while (1 != n) {
result.push_back(osa_k[n]);
n /= osa_k[n];
}
return result;
}
std::vector<std::pair<int, int>> oskPair(int n) {
auto ps = osk(n);
std::vector<std::pair<int, int>> result;
for (int i = 0; i < ps.size();) {
int j = i + 1;
while (j < ps.size() && ps[i] == ps[j])
j++;
result.emplace_back(ps[i], j - i);
i = j;
}
return result;
}
private:
std::vector<int> osa_k;
};
pair<vector<int>, vector<int>> primes_lpf(const int n) {
vector<int> primes;
primes.reserve(n / 10);
vector<int> lpf(n + 1);
for (int i = 2; i <= n; i += 2)
lpf[i] = 2;
for (int i = 3; i <= n; i += 6)
lpf[i] = 3;
if (2 <= n)
primes.push_back(2);
if (3 <= n)
primes.push_back(3);
// 5 * x <= n, x <= floor(n / 5)
const int n5 = n / 5;
int x = 5;
char add_next = 2;
for (; x <= n5; x += add_next, add_next ^= 0x2 ^ 4) {
int px = lpf[x];
if (px == 0) {
lpf[x] = px = x;
primes.push_back(x);
}
for (int i = 2;; ++i) {
int q = primes[i];
int y = q * x;
if (y > n)
break;
lpf[y] = q;
if (q == px)
break;
}
}
for (; x <= n; x += add_next, add_next ^= 0x2 ^ 4) {
if (lpf[x] == 0) {
lpf[x] = x;
primes.push_back(x);
}
}
return {move(primes), move(lpf)};
}
constexpr int PSIZE = 1000000;
auto [primes, lpf] = primes_lpf(PSIZE);
vector<pair<int, int>>& factorize_lv(int x) {
int ps[10], cs[10];
int sz = 0;
while (x != 1) {
int p = lpf[x], c = 0;
do {
x /= p;
c++;
} while (x % p == 0);
ps[sz] = p;
cs[sz] = c;
sz++;
}
static vector<pair<int, int>> fs;
fs.clear();
for (int i = 0; i < sz; i++)
fs.emplace_back(ps[i], cs[i]);
return fs;
}
struct LCA {
int n;
vector<int> idx;
struct S {
int v, depth;
};
vector<vector<S>> spt;
static constexpr S min(S x, S y) { return x.depth < y.depth ? x : y; }
LCA(const std::vector<std::vector<int>>& g, int root)
: n(g.size()), idx(n, -1) {
assert(0 <= root && root < n);
vector<S> tour;
auto dfs = [&](auto&& self, int u, int d) -> void {
idx[u] = tour.size();
tour.emplace_back(u, d);
for (int v : g[u])
if (idx[v] == -1) {
self(self, v, d + 1);
tour.emplace_back(u, d);
}
};
dfs(dfs, root, 0);
int m = tour.size();
int w = bit_width(m + 0U);
spt.resize(w);
spt[0] = move(tour);
for (int k = 0; k + 1 < w; k++) {
int k2 = 1 << k;
int sz = m - 2 * k2 + 1;
spt[k + 1].resize(sz);
for (int i = 0; i < sz; i++)
spt[k + 1][i] = min(spt[k][i], spt[k][i + k2]);
}
}
int lca(int u, int v) {
int l = idx[u], r = idx[v];
if (l > r)
swap(l, r);
int k = bit_width(r - l + 1U) - 1;
return min(spt[k][l], spt[k][r + 1 - (1 << k)]).v;
}
};
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n;
cin >> n;
vector<int> a(n);
rep(i, n) cin >> a[i];
vector to(n, vector<int>());
// Tree tr(n, 0);
rep(i, n - 1) {
int u, v;
cin >> u >> v;
u--, v--;
to[u].push_back(v);
to[v].push_back(u);
// tr.unite(u, v);
}
LCA lca(to, 0);
// tr.init();
vector<int> order(n);
iota(all(order), 0);
std::sort(order.begin(), order.end(), [&](int l, int r) {
// return tr.dfsOrder[l] < tr.dfsOrder[r];
return lca.idx[l] < lca.idx[r];
});
Osa_k osak;
osak.init();
vector ps(1e6, vector<int>());
/*for (auto e : order) {
for (auto[p, q] : osak.oskPair(a[e])) {
ps[p].push_back(e);
}
}*/
for (int v : order) {
for (auto [p, e] : factorize_lv(a[v])) {
ps[p].emplace_back(v);
}
}
vector<mint> ans(n);
rep(i, n) ans[i] = a[i];
rep(p, ps.size()) {
if (ps[p].empty())
continue;
mint ip = mint(p).inv();
auto ids = move(ps[p]);
while (!ids.empty()) {
int sz = ids.size();
rep(i, sz - 1) {
int j = i + 1;
ans[lca.lca(ids[i], ids[j])] *= ip;
}
int nsz = 0;
rep(i, sz) {
int v = ids[i];
a[v] /= p;
if (a[v] % p)
continue;
ids[nsz++] = v;
}
ids.resize(nsz);
}
}
rrep(i, n) {
int v = order[i];
for (auto u : to[v])
if (lca.idx[u] < lca.idx[v]) {
ans[u] *= ans[v];
}
}
for (auto e : ans)
cout << e.val() << '\n';
return 0;
}