結果

問題 No.3250 最小公倍数
ユーザー tassei903
提出日時 2025-08-29 22:05:47
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 4,009 bytes
コンパイル時間 3,361 ms
コンパイル使用メモリ 294,328 KB
実行使用メモリ 176,972 KB
最終ジャッジ日時 2025-08-29 22:06:20
合計ジャッジ時間 27,405 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18 TLE * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define ov4(a, b, c, d, name, ...) name
#define rep3(i, a, b, c) for(ll i = (a); i < (b); i += (c))
#define rep2(i, a, b) rep3(i, a, b, 1)
#define rep1(i, n) rep2(i, 0, n)
#define rep0(n) rep1(aaaaa, n)
#define rep(...) ov4(__VA_ARGS__, rep3, rep2, rep1, rep0)(__VA_ARGS__)
#define per(i, a, b) for(ll i = (a)-1; i >= (b); i--)
#define fore(e, v) for(auto&& e : v)
#define all(a) begin(a), end(a)
#define sz(a) (int)(size(a))
#define lb(v, x) (lower_bound(all(v), x) - begin(v))
#define eb emplace_back

template<typename T, typename S> bool chmin(T& a, const S& b) { return a > b ? a = b, 1 : 0; }
template<typename T, typename S> bool chmax(T& a, const S& b) { return a < b ? a = b, 1 : 0; }
 
const int INF = 1e9 + 100;
const ll INFL = 3e18 + 100;
 
#define i128 __int128_t
 
struct _ {
   _() { cin.tie(0)->sync_with_stdio(0), cout.tie(0); }
} __;

void debug(auto ...vs) {
    ((cerr << vs << " "), ...) << endl;
}

ll safe_div(ll a, ll b) { // floored division
		return a / b - ((a ^ b) < 0 && a % b);
}

ll safe_mod(ll a, ll b) {
    return (a % b + b) % b;
}


constexpr int mod = 998244353;
struct mint {
   int x;
   mint(ll x_ = 0) : x(x_ % mod) {
      if(x < 0) x += mod;
   }
   mint operator-() {
      auto res = *this;
      res.x = (x ? mod - x : 0);
      return res;
   }
   mint& operator+=(mint r) {
      if((x += r.x) >= mod) x -= mod;
      return *this;
   }
   mint& operator-=(mint r) {
      if((x -= r.x) < 0) x += mod;
      return *this;
   }
   mint& operator*=(mint r) {
      x = 1LL * x * r.x % mod;
      return *this;
   }
   mint& operator/=(mint r) { return *this *= r.inv(); }
   friend mint operator+(mint a, mint b) { return a += b; }
   friend mint operator-(mint a, mint b) { return a -= b; }
   friend mint operator*(mint a, mint b) { return a *= b; }
   friend mint operator/(mint a, mint b) { return a /= b; }
   mint inv() const { return pow(mod - 2); }
   mint pow(ll b) const {
      mint a = *this, c = 1;
      while(b) {
         if(b & 1) c *= a;
         a *= a;
         b >>= 1;
      }
      return c;
   }
};
using vm = vector<mint>;


void solve() {
    int n;cin >> n;
    vi a(n);
    rep(i, n) cin >> a[i];
    vector<vi> g(n);
    rep(i, n-1) {
        int u, v;cin >> u >> v;
        u--, v--;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    int m = 1e6 + 1;
    vi mbs(m, -1);
    rep(i, 2, m) {
        if (mbs[i] == -1) {
            rep(j, i, m, i) {
                if (mbs[j]== -1) {
                    mbs[j] = i;
                }
            }
        }
    }  
    vector<vm> invv(m, vm(23, 1));
    rep(i, 2, m) {
        if (mbs[i] != i) continue;
        invv[i][1] = mint(i).inv();
        rep(j, 2, 23) {
            invv[i][j] = invv[i][j-1] * invv[i][1];
        }
    }

    auto factorize = [&](int x) -> unordered_map<int, int> {
        unordered_map<int, int> res;
        while (x > 1) {
            int p = mbs[x];
            while (x % p == 0) {
                res[p] += 1;
                x /= p;
            }
        }
        return res;
    };
    vm ans(n);
    auto dfs = [&](auto self, int v, int p = -1) -> pair<mint, unordered_map<int, int>> {
        auto mp = factorize(a[v]);
        mint res = a[v];
        for (auto u : g[v]) {
            if (p == u) continue;
            auto [res2, mp2] = self(self, u, v);
            if (sz(mp2) > sz(mp)) {
                swap(mp2, mp);
            }
            res *= res2;
            for(auto [x, y] : mp2) {
                res *= invv[x][min(mp[x], y)];
                mp[x] = max(mp[x], y);
            }
        }
        ans[v] = res;
        return {res, mp};
    };

    auto [res, _] = dfs(dfs, 0);

    rep(i, n) {
        cout << ans[i].x << endl;
    }

}


int main() {

    // int T;cin >> T;
	int T = 1;
    while(T--) {

        solve();
    }
    
}
0