結果
| 問題 |
No.3250 最小公倍数
|
| ユーザー |
👑  hos.lyric
|
| 提出日時 | 2025-08-29 21:32:22 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,379 ms / 2,000 ms |
| コード長 | 9,422 bytes |
| コンパイル時間 | 2,095 ms |
| コンパイル使用メモリ | 138,748 KB |
| 実行使用メモリ | 288,920 KB |
| 最終ジャッジ日時 | 2025-08-29 21:32:41 |
| 合計ジャッジ時間 | 15,526 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 21 |
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:282:38: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
282 | for (int u = 0; u < N; ++u) scanf("%d", &A[u]);
| ~~~~~^~~~~~~~~~~~~
main.cpp:286:12: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
286 | scanf("%d%d", &U[i], &V[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
ソースコード
#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <chrono>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using Int = long long;
template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")
////////////////////////////////////////////////////////////////////////////////
template <unsigned M_> struct ModInt {
static constexpr unsigned M = M_;
unsigned x;
constexpr ModInt() : x(0U) {}
constexpr ModInt(unsigned x_) : x(x_ % M) {}
constexpr ModInt(unsigned long long x_) : x(x_ % M) {}
constexpr ModInt(int x_) : x(((x_ %= static_cast<int>(M)) < 0) ? (x_ + static_cast<int>(M)) : x_) {}
constexpr ModInt(long long x_) : x(((x_ %= static_cast<long long>(M)) < 0) ? (x_ + static_cast<long long>(M)) : x_) {}
ModInt &operator+=(const ModInt &a) { x = ((x += a.x) >= M) ? (x - M) : x; return *this; }
ModInt &operator-=(const ModInt &a) { x = ((x -= a.x) >= M) ? (x + M) : x; return *this; }
ModInt &operator*=(const ModInt &a) { x = (static_cast<unsigned long long>(x) * a.x) % M; return *this; }
ModInt &operator/=(const ModInt &a) { return (*this *= a.inv()); }
ModInt pow(long long e) const {
if (e < 0) return inv().pow(-e);
ModInt a = *this, b = 1U; for (; e; e >>= 1) { if (e & 1) b *= a; a *= a; } return b;
}
ModInt inv() const {
unsigned a = M, b = x; int y = 0, z = 1;
for (; b; ) { const unsigned q = a / b; const unsigned c = a - q * b; a = b; b = c; const int w = y - static_cast<int>(q) * z; y = z; z = w; }
assert(a == 1U); return ModInt(y);
}
ModInt operator+() const { return *this; }
ModInt operator-() const { ModInt a; a.x = x ? (M - x) : 0U; return a; }
ModInt operator+(const ModInt &a) const { return (ModInt(*this) += a); }
ModInt operator-(const ModInt &a) const { return (ModInt(*this) -= a); }
ModInt operator*(const ModInt &a) const { return (ModInt(*this) *= a); }
ModInt operator/(const ModInt &a) const { return (ModInt(*this) /= a); }
template <class T> friend ModInt operator+(T a, const ModInt &b) { return (ModInt(a) += b); }
template <class T> friend ModInt operator-(T a, const ModInt &b) { return (ModInt(a) -= b); }
template <class T> friend ModInt operator*(T a, const ModInt &b) { return (ModInt(a) *= b); }
template <class T> friend ModInt operator/(T a, const ModInt &b) { return (ModInt(a) /= b); }
explicit operator bool() const { return x; }
bool operator==(const ModInt &a) const { return (x == a.x); }
bool operator!=(const ModInt &a) const { return (x != a.x); }
friend std::ostream &operator<<(std::ostream &os, const ModInt &a) { return os << a.x; }
};
////////////////////////////////////////////////////////////////////////////////
constexpr unsigned MO = 998244353;
using Mint = ModInt<MO>;
// !!!Watch out for stack overflow!!!
// Meldable
// 0 for null, ts[0] = T()
// chPoint(u, a, f, args...): point update
// chRange(u, a, b, f, args...): range update s.t. T() -> T()
// T::push(T *l, T *r)
// T::pull(const T &l, const T &r)
// T::meld(const T &t): meld leaf T's
template <class T> struct Seg {
static constexpr int NUM_NODES = 1 << 25;
int l0, r0;
int nodesLen;
int ls[NUM_NODES], rs[NUM_NODES];
T ts[NUM_NODES];
void init(int l0_, int r0_) {
l0 = l0_;
r0 = r0_;
nodesLen = 1;
ls[0] = rs[0] = 0;
ts[0] = T();
}
int newNode() {
assert(nodesLen < NUM_NODES);
const int u = nodesLen++;
ls[u] = rs[u] = 0;
ts[u] = T();
return u;
}
void push(int u) {
ts[u].push(ls[u] ? &ts[ls[u]] : nullptr, rs[u] ? &ts[rs[u]] : nullptr);
}
void pull(int u) {
ts[u].pull(ts[ls[u]], ts[rs[u]]);
}
template <class F, class... Args>
void chPoint(int &u, int l, int r, int a, F f, Args &&... args) {
if (!u) u = newNode();
if (l + 1 == r) {
(ts[u].*f)(args...);
return;
}
const int mid = l + ((r - l) >> 1);
push(u);
(a < mid)
? chPoint(ls[u], l, mid, a, f, args...)
: chPoint(rs[u], mid, r, a, f, args...);
pull(u);
}
template <class F, class... Args>
void chPoint(int &u, int a, F f, Args &&... args) {
assert(l0 <= a); assert(a < r0);
chPoint(u, l0, r0, a, f, args...);
}
template <class F, class... Args>
void chRange(int &u, int l, int r, int a, int b, F f, Args &&... args) {
if (!u) return;
if (b <= l || r <= a) return;
if (a <= l && r <= b) {
(ts[u].*f)(args...);
return;
}
const int mid = l + ((r - l) >> 1);
push(u);
chRange(ls[u], l, mid, a, b, f, args...);
chRange(rs[u], mid, r, a, b, f, args...);
pull(u);
}
template <class F, class... Args>
void chRange(int &u, int a, int b, F f, Args &&... args) {
assert(l0 <= a); assert(a <= b); assert(b <= r0);
chRange(u, l0, r0, a, b, f, args...);
}
T get(int u, int l, int r, int a, int b) {
if (!u) return T();
if (b <= l || r <= a) return T();
if (a <= l && r <= b) return ts[u];
const int mid = l + ((r - l) >> 1);
push(u);
const T tL = get(ls[u], l, mid, a, b);
const T tR = get(rs[u], mid, r, a, b);
pull(u);
T t;
t.pull(tL, tR);
return t;
}
T get(int u, int a, int b) {
assert(l0 <= a); assert(a <= b); assert(b <= r0);
return get(u, l0, r0, a, b);
}
template <class F, class... Args>
int findLeft(int u, int l, int r, int b, F f, Args &&... args) {
if (!u || b <= l || (r <= b && !(ts[u].*f)(args...))) return l - 1;
if (r - l == 1) return l;
const int mid = l + ((r - l) >> 1);
push(u);
const int aR = findLeft(rs[u], mid, r, b, f, args...);
if (mid <= aR) return aR;
const int aL = findLeft(ls[u], l, mid, b, f, args...);
return aL;
}
template <class F, class... Args>
int findLeft(int u, int b, F f, Args &&... args) {
assert(l0 <= b); assert(b <= r0);
if ((T().*f)(args...)) return b;
return findLeft(u, l0, r0, b, f, args...);
}
// Frees v.
int meld(int u, int v, int l, int r) {
if (!u) return v;
if (!v) return u;
if (l + 1 == r) {
ts[u].meld(ts[v]);
return u;
}
const int mid = l + ((r - l) >> 1);
push(u);
push(v);
ls[u] = meld(ls[u], ls[v], l, mid);
rs[u] = meld(rs[u], rs[v], mid, r);
pull(u);
return u;
}
int meld(int u, int v) {
return meld(u, v, l0, r0);
}
/*
void print(int depth, int u, int l, int r) const {
if (!u) return;
cerr << string(2 * depth, ' ') << u << " [" << l << ", " << r << ") " << ts[u] << endl;
if (l + 1 == r) return;
const int mid = l + ((r - l) >> 1);
print(depth + 1, ls[u], l, mid);
print(depth + 1, rs[u], mid, r);
}
void print(int u) const {
if (!u) cerr << "[Seg::print] null" << endl;
print(0, u, l0, r0);
}
//*/
};
struct Node {
Mint prod;
Node() : prod(1) {}
void push(Node *, Node *) {
}
void pull(const Node &l, const Node &r) {
prod = l.prod * r.prod;
}
void meld(const Node &t) {
// 1 or p^e
chmax(prod.x, t.prod.x);
}
void change(Mint val) {
prod = val;
}
};
int N;
vector<int> A;
vector<int> U, V;
int maxA;
vector<int> lpf;
vector<vector<int>> graph;
vector<Mint> ans;
Seg<Node> seg;
int dfs(int u, int p) {
int ret = 0;
for (const int v : graph[u]) if (p != v) {
const int res = dfs(v, u);
ret = seg.meld(ret, res);
}
for (int a = A[u]; a > 1; ) {
const int p = lpf[a];
int e = 0;
do { ++e; a /= p; } while (a % p == 0);
int q = 1;
for (int f = 1; f <= e; ++f) {
q *= p;
seg.chPoint(ret, q, &Node::change, Mint(p));
}
}
ans[u] = seg.ts[ret].prod;
return ret;
}
int main() {
for (; ~scanf("%d", &N); ) {
A.resize(N);
for (int u = 0; u < N; ++u) scanf("%d", &A[u]);
U.resize(N - 1);
V.resize(N - 1);
for (int i = 0; i < N - 1; ++i) {
scanf("%d%d", &U[i], &V[i]);
--U[i];
--V[i];
}
maxA = *max_element(A.begin(), A.end());
lpf.assign(maxA + 1, 0);
for (int p = 2; p <= maxA; ++p) lpf[p] = p;
for (int p = 2; p <= maxA; ++p) if (lpf[p] == p) {
for (int n = p; n <= maxA; n += p) chmin(lpf[n], p);
}
graph.assign(N, {});
for (int i = 0; i < N - 1; ++i) {
graph[U[i]].push_back(V[i]);
graph[V[i]].push_back(U[i]);
}
ans.assign(N, 0);
seg.init(0, maxA + 1);
dfs(0, -1);
for (int u = 0; u < N; ++u) {
printf("%u\n", ans[u].x);
}
}
return 0;
}