結果

問題 No.3250 最小公倍数
コンテスト
ユーザー shinchan
提出日時 2025-08-30 01:28:27
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 7,915 bytes
コンパイル時間 2,607 ms
コンパイル使用メモリ 225,880 KB
実行使用メモリ 226,316 KB
最終ジャッジ日時 2025-10-16 16:51:49
合計ジャッジ時間 34,065 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 5 WA * 1 TLE * 13 -- * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

#define all(v) (v).begin(),(v).end()
#define pb emplace_back
#define rep(i, n) for(int i=0;i<(n);i++)
#define foa(e, v) for(auto& e : v)
#define dout(a) cout<<fixed<<setprecision(10)<<a<<'\n';
#define Cout(a) cout<<a<<'\n';

using ll = long long;
using ld = long double;
using Int = __int128;
template <class T> using pqr = priority_queue<T, vector<T>, greater<T>>;

template <typename T1, typename T2> inline bool chmax(T1 &a, T2 b) {
    bool compare = a < b;
    if(compare) a = b;
    return compare;
}
template <typename T1, typename T2> inline bool chmin(T1 &a, T2 b) {
    bool compare = a > b;
    if(compare) a = b;
    return compare;
}
template <typename T> inline T back(std::set<T> &s) {
    return *s.rbegin();
}
template <typename T> inline T back(std::multiset<T> &s) {
    return *s.rbegin();
}
template <typename T> inline T pop_back(std::set<T> &s) {
    auto it = prev(s.end());
    T val = *it;
    s.erase(it); 
    return val;
}
template <typename T> inline T pop_back(std::multiset<T> &s) {
    auto it = prev(s.end());
    T val = *it;
    s.erase(it); 
    return val;
}

const int dy[8] = {-1, 0, 0, 1, 1, -1, 1, -1};
const int dx[8] = {0, -1, 1, 0, -1, -1, 1, 1};

const ll MOD7 = 1000000007, MOD998 = 998244353, INF = (3LL << 59);
const int inf = 1 << 30;
const char br = '\n';

ll modinv(ll a, ll MOD) {
   ll b = MOD, u = 1, v = 0;
   while(b) {
      ll t = a / b;
      a -= t * b;
      swap(a, b);
      u -= t * v;
      swap(u, v);
   }
   u %= MOD;
   if(u < 0) u += MOD;
   return u;
}

ll modpow(ll a, ll n, ll MOD) {
   using T = __int128_t;
   // using T = ll;
   T res = 1;
   T mul = a;
   mul %= MOD;
   if(n < 0) {
      n = -n;
      mul = modinv(mul, MOD);
   }
   while(n > 0) {
      if(n & 1) res = (res * mul) % MOD;
      mul = (mul * mul) % MOD;
      n >>= 1;
   }
   return ll(res);
}

bool is_prime(ll N) {
   if(N == 2) return true;
   if(N == 1 || N % 2 == 0) return false;
   ll s = 0;
   ll d = N - 1;
   while(d % 2 == 0) {
      s++;
      d /= 2;
   }
   vector<ll> tests = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
   for(auto a : tests) {
      if(a == N) continue;
      ll X = modpow(a, d, N);
      int r = 0;
      if(X == 1) { continue; }
      while(X != N - 1) {
         X = modpow(X, 2, N);
         r++;
         if(X == 1 || r == s) return false;
      }
   }
   return true;
}

ll find_prime_factor(ll N) {
   using i128 = __int128_t;
   if(N % 2 == 0) { return 2; }
   int b = int(sqrt(sqrt(sqrt(N)))) + 1;
   for(ll c = 1; c < N; c++) {
      auto f = [&](ll a) -> ll { return modpow(a, 2, N) + c; };
      ll y = 6;
      ll g = 1;
      i128 q = 1;
      int r = 1;
      int k = 0;
      ll ys = 0;
      ll x = 0;
      while(g == 1) {
         x = y;
         while(k < 3 * r / 4) {
            y = f(y);
            k++;
         }
         while(k < r && g == 1) {
            ys = y;
            for(ll i = 0; i < min(b, r - k); i++) {
               y = f(y);
               q *= abs(x - y);
               q %= N;
            }
            g = gcd(ll(q), N);
            k += b;
         }
         k = r;
         r *= 2;
      }
      if(g == N) {
         g = 1;
         y = ys;
         while(g == 1) {
            y = f(y);
            g = gcd(abs(x - y), N);
         }
      }
      if(g == N) { continue; }
      if(is_prime(g)) { return g; }
      if(is_prime(N / g)) { return N / g; }
      return find_prime_factor(g);
   }
   assert(false);
}

vector<pair<ll, ll>> factorize(ll N) {
   vector<pair<ll, ll>> ret;
   while(!is_prime(N) && N > 1) {
      ll p = find_prime_factor(N);
      int s = 0;
      while(N % p == 0) {
         N /= p;
         s++;
      }
      ret.pb(p, s);
   }
   if(N > 1) { ret.pb(N, 1); }
   return ret;
}

template<int MOD> struct Modint {
    long long val;
    constexpr Modint(long long v = 0) noexcept : val(v % MOD) { if (val < 0) val += MOD; }
    constexpr int mod() const { return MOD; }
    constexpr long long value() const { return val; }
    constexpr Modint operator - () const noexcept { return val ? MOD - val : 0; }
    constexpr Modint operator + (const Modint& r) const noexcept { return Modint(*this) += r; }
    constexpr Modint operator - (const Modint& r) const noexcept { return Modint(*this) -= r; }
    constexpr Modint operator * (const Modint& r) const noexcept { return Modint(*this) *= r; }
    constexpr Modint operator / (const Modint& r) const noexcept { return Modint(*this) /= r; }
    constexpr Modint& operator += (const Modint& r) noexcept {
        val += r.val;
        if (val >= MOD) val -= MOD;
        return *this;
    }
    constexpr Modint& operator -= (const Modint& r) noexcept {
        val -= r.val;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr Modint& operator *= (const Modint& r) noexcept {
        val = val * r.val % MOD;
        return *this;
    }
    constexpr Modint& operator /= (const Modint& r) noexcept {
        long long a = r.val, b = MOD, u = 1, v = 0;
        while (b) {
            long long t = a / b;
            a -= t * b, swap(a, b);
            u -= t * v, swap(u, v);
        }
        val = val * u % MOD;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr bool operator == (const Modint& r) const noexcept { return this->val == r.val; }
    constexpr bool operator != (const Modint& r) const noexcept { return this->val != r.val; }
    friend constexpr istream& operator >> (istream& is, Modint<MOD>& x) noexcept {
        is >> x.val;
        x.val %= MOD;
        if (x.val < 0) x.val += MOD;
        return is;
    }
    friend constexpr ostream& operator << (ostream& os, const Modint<MOD>& x) noexcept {
        return os << x.val;
    }
    constexpr Modint<MOD> pow(long long n) noexcept {
        if (n == 0) return 1;
        if (n < 0) return this->pow(-n).inv();
        Modint<MOD> ret = pow(n >> 1);
        ret *= ret;
        if (n & 1) ret *= *this;
        return ret;
    }
    constexpr Modint<MOD> inv() const noexcept {
        long long a = this->val, b = MOD, u = 1, v = 0;
        while (b) {
            long long t = a / b;
            a -= t * b, swap(a, b);
            u -= t * v, swap(u, v);
        }
        return Modint<MOD>(u);
    }
};

const int MOD = MOD998;
using mint = Modint<MOD>;

void solve() {
    int n; cin >> n;
    vector<ll> a(n);
    rep(i, n) cin >> a[i];
    vector<vector<int>> v(n);
    rep(i, n - 1) {
        int x, y; cin >> x >> y;
        x --; y --;
        v[x].pb(y);
        v[y].pb(x);
    }
    vector<mint> ans(n, 1);
    vector<map<ll, ll>> mp(n);
    int N = 1000000;
    vector<vector<mint>> po(N + 1);

    ll lim = (1LL << 28);
    for(ll i = 2; i <= N; i ++) {
        po[i].pb(1);
        ll now = 1;
        while(now * i <= lim) {
            now *= i;
            po[i].pb(now);
        }
    }

    auto dfs = [&](auto &&dfs, int now, int p) -> void {
        for(auto [x, y] : factorize(a[now])) {
            chmax(mp[now][x], y);
        }
        
        ans[now] = a[now];
        if(v[now].empty() and now == 0) return;
        if((int)v[now].size() == 1) return;
        vector<int> ord;
        foa(e, v[now]) {
            if(e == p) continue;
            dfs(dfs, e, now);
            ord.pb(e);
        }
        sort(all(ord), [&](int i, int j) {return mp[i].size() < mp[j].size();});
        swap(mp[now], mp[ord.back()]);
        ans[now] = ans[ord.back()];
        foa(e, ord) {
            for(auto [x, y] : mp[e]) {
                if(y > mp[now][x]) {
                    ans[now] *= po[x][y - mp[now][x]];
                    mp[now][x] = y;
                }
            }
        }
    };
    dfs(dfs, 0, -1);
    foa(e, ans) Cout(e);
}

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

    int testcase = 1; 
    // cin >> testcase;
    while(testcase --) solve();

    return 0;
}
0