結果

問題 No.3250 最小公倍数
コンテスト
ユーザー jiangxinyang
提出日時 2025-08-06 10:58:28
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,827 ms / 2,000 ms
コード長 3,711 bytes
コンパイル時間 1,907 ms
コンパイル使用メモリ 201,016 KB
実行使用メモリ 272,088 KB
最終ジャッジ日時 2025-11-09 23:03:49
合計ジャッジ時間 21,570 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 23
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:83:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   83 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
main.cpp:84:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   84 |     fp(i, 1, n) scanf("%d", &a[i]), chkmax(mx, a[i]);
      |                 ~~~~~^~~~~~~~~~~~~
main.cpp:87:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   87 |         scanf("%d%d", &u, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~

ソースコード

diff # 

#include <bits/stdc++.h>
#define fp(i, a, b) for (int i(a), ed(b); i <= ed; ++i)
#define fb(i, a, b) for (int i(a), ed(b); i >= ed; --i)
#define go(u, i) for (int i(head[u]); i; i = e[i].nxt)
using namespace std;
typedef long long Int;
typedef pair<int, int> pii;
////////////////////////////////////////////////////////////////////////////////////////////////////
template <typename T1, typename T2>
inline void chkmin(T1 &a, T2 b) {
    if (a > b) a = b;
}
template <typename T1, typename T2>
inline void chkmax(T1 &a, T2 b) {
    if (a < b) a = b;
}
const int maxn = 5e5 + 10, maxm = 1e6 + 10, mod = 998244353;
int n, a[maxn], mx, f[maxn], ans[maxn];
int pri[maxm / 10], cnt, v[maxm], pw[maxm / 10][20], ipw[maxm / 10][20];
vector<int> g1[maxn], g2[maxn], mult[maxm / 10];
int dep[maxn], elr[maxn << 1], len, pos[maxn << 1], lg[maxn << 1];
pair<int, int> st[maxn << 1][20];
int stk[maxn], tp;
inline int fpow(int a, int b, int ans = 1) {
    for (; b; b >>= 1, a = 1ll * a * a % mod)
        if (b & 1) ans = 1ll * ans * a % mod;
    return ans;
}
inline void init(const int &n) {
    fp(i, 2, n) {
        if (!v[i]) pri[v[i] = ++cnt] = i;
        for (int j = 1; j <= cnt && pri[j] * i <= n; ++j) {
            v[i * pri[j]] = j;
            if (i % pri[j] == 0) break;
        }
    }
    fp(i, 1, cnt) {
        int inv = fpow(pri[i], mod - 2);
        pw[i][0] = ipw[i][0] = 1;
        fp(j, 1, 19) pw[i][j] = 1ll * pw[i][j - 1] * pri[i] % mod, ipw[i][j] = 1ll * ipw[i][j - 1] * inv % mod;
    }
}
void dfs1(int u, int pre) {
    elr[pos[u] = ++len] = u, dep[u] = dep[pre] + 1;
    for (auto &v : g1[u])
        if (v != pre) dfs1(v, u), elr[++len] = u;
}
inline int getlca(int u, int v) {
    int l = min(pos[u], pos[v]), r = max(pos[u], pos[v]), d = lg[r - l + 1];
    return min(st[l][d], st[r - (1 << d) + 1][d]).second;
}
inline void link(const int &u, const int &v) {
    f[u] = f[v] = 0, g2[u].push_back(v);
}
inline void ins(const int &u) {
    if (!tp) return stk[tp = 1] = u, void();
    int lca = getlca(u, stk[tp]);
    if (lca == stk[tp]) return stk[++tp] = u, void();
    while (tp > 1 && pos[stk[tp - 1]] >= pos[lca]) link(stk[tp - 1], stk[tp]), --tp;
    if (lca != stk[tp]) link(lca, stk[tp]), stk[tp] = lca;
    stk[++tp] = u;
}
inline void build(const int &id) {
    for (auto &u : mult[id]) ins(u);
    fp(i, 2, tp) link(stk[i - 1], stk[i]);
    for (auto &u : mult[id]) {
        int x = a[u], cnt = 0;
        while (x % pri[id] == 0) x /= pri[id], ++cnt;
        f[u] = cnt;
    }
}
void dfs2(int u, int fa, const int &id) {
    for (auto &v : g2[u]) dfs2(v, u, id), chkmax(f[u], f[v]);
    ans[u] = 1ll * ans[u] * pw[id][f[u]] % mod;
    ans[fa] = 1ll * ans[fa] * ipw[id][f[u]] % mod;
    g2[u].clear();
}
void dfs3(int u, int pre) {
    for (auto &v : g1[u])
        if (v != pre) dfs3(v, u), ans[u] = 1ll * ans[u] * ans[v] % mod;
}
int main() {
    scanf("%d", &n);
    fp(i, 1, n) scanf("%d", &a[i]), chkmax(mx, a[i]);
    fp(i, 2, n) {
        int u, v;
        scanf("%d%d", &u, &v);
        g1[u].push_back(v), g1[v].push_back(u);
    }
    init(mx), dfs1(1, 0);
    fp(i, 1, cnt) mult[i].push_back(1);
    fp(i, 2, len) if (pos[elr[i]] == i) {
        int x = a[elr[i]], id;
        while (x > 1) {
            id = v[x], mult[id].push_back(elr[i]);
            while (x % pri[id] == 0) x /= pri[id];
        }
    }
    fp(i, 2, len) lg[i] = lg[i >> 1] + 1;
    fp(i, 1, len) st[i][0] = {dep[elr[i]], elr[i]};
    fp(j, 0, 18) for (int i = 1; i + (1 << j) <= len; ++i) st[i][j + 1] = min(st[i][j], st[i + (1 << j)][j]);
    fp(i, 1, n) ans[i] = 1;
    fp(i, 1, cnt) tp = 0, build(i), dfs2(1, 0, i);
    dfs3(1, 0);
    fp(i, 1, n) printf("%d\n", ans[i]);
    return 0;
}
0