結果

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

ソースコード

diff # 

/*
(n,),a,*e=[[*map(int,s.split())]for s in open(0)]
M=998244353
def pf(n):
 a,f={},2
 while f*f<=n:
  if n%f:f+=1
  else:a[f]=a.get(f,0)+1;n//=f
 if n>1:a[n]=a.get(n,0)+1
 return a
g=[[]for _ in range(n)]
for u,v in e:
  g[u-1]+=v-1,
  g[v-1]+=u-1,
q=[(0,-1,0)]
l=[pf(i)for i in a]
ans=[1]*n
while q:
  p,z,s=q.pop()
  if s:
    r=0
    for k,v in l[p].items():
      ans[p]*=pow(k,v,M)
      ans[p]%=M
    if len(l[z])<len(l[p]):
      r=1
      z,p=p,z
    for k,v in l[p].items():
      if k in l[z]:
        l[z][k]=max(l[z][k],v)
      else:
        l[z][k]=v
    if r:
      l[p],l[z]=l[z],l[p]
    continue
  for v in g[p]:
    if v!=z:
      q+=(v,p,1),(v,p,0),
for k,v in l[0].items():
  ans[0]*=pow(k,v,M)
  ans[0]%=M
print(*ans,sep='\n')
*/

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

// prime factorization function
map<ll,int> pf(ll n) {
    map<ll,int> a;
    ll f = 2;
    while (f * f <= n) {
        if (n % f) {
            f += 1;
        } else {
            a[f] += 1;
            n /= f;
        }
    }
    if (n > 1) a[n] += 1;
    return a;
}

// modular exponentiation
ll modpow(ll base, ll exp, ll mod) {
    ll res = 1 % mod;
    while (exp > 0) {
        if (exp & 1) res = (__int128)res * base % mod;
        base = (__int128)base * base % mod;
        exp >>= 1;
    }
    return res;
}

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

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

    // l = [pf(i) for i in a]
    vector<map<ll,int>> l(n);
    for (int i = 0; i < n; i++) {
        l[i] = pf(a[i]);
    }

    vector<ll> ans(n, 1);

    // q = [(0,-1,0)]
    vector<tuple<int,int,int>> q;
    q.emplace_back(0, -1, 0);

    while (!q.empty()) {
        auto [p,z,s] = q.back();
        q.pop_back();
        if (s) {
            int r = 0;
            for (auto [k,v] : l[p]) {
                ans[p] = ans[p] * modpow(k,v,M) % M;
            }
            if (z != -1 && l[z].size() < l[p].size()) {
                r = 1;
                swap(z,p);
            }
            if (z != -1) {
                for (auto [k,v] : l[p]) {
                    auto it = l[z].find(k);
                    if (it != l[z].end()) {
                        it->second = max(it->second, v);
                    } else {
                        l[z][k] = v;
                    }
                }
                if (r) {
                    swap(l[p], l[z]);
                }
            }
            continue;
        }
        for (int v : g[p]) {
            if (v != z) {
                q.emplace_back(v,p,1);
                q.emplace_back(v,p,0);
            }
        }
    }

    for (auto [k,v] : l[0]) {
        ans[0] = ans[0] * modpow(k,v,M) % M;
    }

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

    return 0;
}
0