結果

問題 No.3250 最小公倍数
ユーザー mkawa2
提出日時 2025-08-29 23:33:25
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,834 bytes
コンパイル時間 3,506 ms
コンパイル使用メモリ 296,548 KB
実行使用メモリ 241,744 KB
最終ジャッジ日時 2025-08-29 23:33:52
合計ジャッジ時間 23,153 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18 TLE * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int md = 998244353;

// 高速累乗 (a^e mod m)
ll modpow(ll a, ll e, ll m) {
    ll res = 1;
    while (e > 0) {
        if (e & 1) res = res * a % m;
        a = a * a % m;
        e >>= 1;
    }
    return res;
}

// 素数篩
struct Sieve {
    int n;
    vector<int> plist;
    vector<int> min_prime_factor;

    Sieve(int n_) {
        n = n_;
        min_prime_factor.assign(n+1, 0);
        min_prime_factor[0] = min_prime_factor[1] = 1;
        plist.push_back(2);
        for (int i = 2; i <= n; i += 2) min_prime_factor[i] = 2;
        for (int x = 3; x <= n; x += 2) {
            if (min_prime_factor[x] == 0) {
                min_prime_factor[x] = x;
                plist.push_back(x);
                if ((ll)x * x > n) continue;
                for (ll y = 1LL * x * x; y <= n; y += 2LL * x) {
                    if (min_prime_factor[y] == 0) min_prime_factor[y] = x;
                }
            }
        }
    }

    bool isprime(int x) {
        return min_prime_factor[x] == x;
    }

    // 素因数分解 (素数 → 指数)
    map<int,int> pf(int x) {
        map<int,int> p2e;
        while (x > 1) {
            int mpf = min_prime_factor[x];
            p2e[mpf]++;
            x /= mpf;
        }
        return p2e;
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> aa(n);
    for (int i=0;i<n;i++) cin >> aa[i];

    vector<vector<int>> to(n);
    for (int i=0;i<n-1;i++){
        int u,v;
        cin >> u >> v;
        --u; --v;
        to[u].push_back(v);
        to[v].push_back(u);
    }

    vector<int> parent(n, -1), depth(n,0);
    vector<int> uu;
    {
        vector<int> stack = {0};
        while (!stack.empty()) {
            int u = stack.back(); stack.pop_back();
            uu.push_back(u);
            for (int v: to[u]){
                if (v == parent[u]) continue;
                parent[v] = u;
                depth[v] = depth[u]+1;
                stack.push_back(v);
            }
        }
    }

    Sieve sv(1000000);

    vector<ll> ans(n);
    vector< map<int,int> > dp(n);
    for (int i=0;i<n;i++) dp[i] = sv.pf(aa[i]);

    for (int idx = (int)uu.size()-1; idx>=0; idx--){
        int u = uu[idx];
        ans[u] = aa[u];
        if (u == 0) break;
        int v = parent[u];
        if (dp[v].size() < dp[u].size()) {
            swap(dp[v], dp[u]);
            swap(aa[v], aa[u]);
        }
        for (auto [p,e] : dp[u]) {
            if (dp[v][p] < e) {
                int diff = e - dp[v][p];
                ll mul = modpow(p, diff, md);
                aa[v] = (aa[v] * mul) % md;
                dp[v][p] = e;
            }
        }
    }

    for (int i=0;i<n;i++) cout << ans[i] << "\n";

    return 0;
}
0