結果

問題 No.3250 最小公倍数
コンテスト
ユーザー risujiroh
提出日時 2025-08-29 23:09:44
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,554 ms / 2,000 ms
コード長 6,135 bytes
コンパイル時間 4,797 ms
コンパイル使用メモリ 347,592 KB
実行使用メモリ 295,020 KB
最終ジャッジ日時 2025-10-16 16:36:32
合計ジャッジ時間 22,152 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

#if __INCLUDE_LEVEL__ == 0

#include __BASE_FILE__

using Mint = atcoder::modint998244353;

void Solve() {
  int n;
  IN(n);
  vector<int> a(n);
  IN(a);
  int A = ranges::max(a);
  for (int _ : Rep(0, n - 1)) {
    int i, j;
    IN(i, j);
    --i, --j;
    CsrArray<int>::Add(i, j);
    CsrArray<int>::Add(j, i);
  }
  auto g = CsrArray<int>::Build(n);

  linear_sieve::init(A);
  for (int i : Rep1(2, A)) {
    int prv = -1;
    int len = 0;
    for (int p : linear_sieve::factor(i)) {
      if (p != prv) {
        if (prv != -1) {
          CsrArray<pair<int, int>>::Add(i, {prv, len});
        }
        prv = p;
        len = 1;
      } else {
        ++len;
      }
    }
    CsrArray<pair<int, int>>::Add(i, {prv, len});
  }
  auto factors = CsrArray<pair<int, int>>::Build(A + 1);

  for (int p : linear_sieve::primes) {
    int prod = 1;
    for (int e = 0;; ++e) {
      CsrArray<int>::Add(p, prod);
      if (prod > A / p) {
        break;
      }
      prod *= p;
    }
  }
  auto pw = CsrArray<int>::Build(A + 1);

  vector<Mint> out(n);

  vector<HashMap<int, int>> f(n);
  vector<Mint> cur(n);
  Fix([&](auto self, int i, int pv) -> void {
    for (auto [p, e] : factors[a[i]]) {
      f[i][p] = e;
    }
    cur[i] = a[i];
    for (int j : g[i]) {
      if (j == pv) {
        continue;
      }
      self(j, i);
      if (Sz(f[i]) < Sz(f[j])) {
        f[i].swap(f[j]);
        swap(cur[i], cur[j]);
      }
      for (auto [p, e] : f[j]) {
        auto it = f[i].find(p);
        if (it != f[i].end()) {
          int ei = it->second;
          if (ei < e) {
            it->second = e;
            cur[i] *= pw[p][e - ei];
          } else {
            continue;
          }
        } else {
          f[i][p] = e;
          cur[i] *= pw[p][e];
        }
      }
    }
    out[i] = cur[i];
  })(0, -1);

  ranges::for_each(out, LIFT(OUT));
}

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

  Solve();
}

#elif __INCLUDE_LEVEL__ == 1

#include <bits/stdc++.h>

#include <atcoder/modint.hpp>

template <class T, int Id = -1>
class CsrArray {
 public:
  static void Reserve(int m) {
    buf_.reserve(m);
  }

  static void Add(int i, T x) {
    buf_.emplace_back(i, std::move(x));
  }

  static CsrArray Build(int n) {
    CsrArray ret;
    ret.pos_.resize(n + 1);
    for (int i : buf_ | std::views::keys) {
      ++ret.pos_[i];
    }
    std::partial_sum(ret.pos_.begin(), ret.pos_.end(), ret.pos_.begin());
    ret.data_.resize(ret.pos_[n]);
    for (auto& [i, x] : buf_ | std::views::reverse) {
      ret.data_[--ret.pos_[i]] = std::move(x);
    }
    buf_.clear();
    return ret;
  }

  int size() const { return int(pos_.size()) - 1; }

  auto operator[](int i) {
    return std::span<T>(data_.data() + pos_[i], data_.data() + pos_[i + 1]);
  }
  auto operator[](int i) const {
    return std::span<const T>(data_.data() + pos_[i], data_.data() + pos_[i + 1]);
  }

 private:
  static thread_local inline std::vector<std::pair<int, T>> buf_;
  std::vector<T> data_;
  std::vector<int> pos_;
};

#include <ext/pb_ds/assoc_container.hpp>

struct Splitmix64Hash {
  using u64 = std::uint64_t;

  static u64 splitmix64(u64 x) {
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }

  u64 operator()(u64 x) const {
    static const u64 r = std::chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x + r);
  }
};

template <class Key, class T>
using HashMap = __gnu_pbds::gp_hash_table<Key, T, Splitmix64Hash>;

template <class Key>
using HashSet = HashMap<Key, __gnu_pbds::null_type>;

template <class F>
class Fix {
 public:
  explicit Fix(F f) : f_(std::move(f)) {}

  template <class... Ts>
  decltype(auto) operator()(Ts&&... xs) {
    return f_(std::ref(*this), std::forward<Ts>(xs)...);
  }

  template <class... Ts>
  decltype(auto) operator()(Ts&&... xs) const {
    return f_(std::ref(*this), std::forward<Ts>(xs)...);
  }

 private:
  F f_;
};

template <class T> concept MyRange = std::ranges::range<T> && !std::convertible_to<T, std::string_view>;
template <class T> concept MyTuple = std::__is_tuple_like<T>::value && !MyRange<T>;

namespace std {

istream& operator>>(istream& is, MyRange auto&& r) {
  for (auto&& e : r) is >> e;
  return is;
}
istream& operator>>(istream& is, MyTuple auto&& t) {
  apply([&](auto&... xs) { (is >> ... >> xs); }, t);
  return is;
}

ostream& operator<<(ostream& os, MyRange auto&& r) {
  auto sep = "";
  for (auto&& e : r) os << exchange(sep, " ") << e;
  return os;
}
ostream& operator<<(ostream& os, MyTuple auto&& t) {
  auto sep = "";
  apply([&](auto&... xs) { ((os << exchange(sep, " ") << xs), ...); }, t);
  return os;
}

template <class T, atcoder::internal::is_modint_t<T>* = nullptr>
istream& operator>>(istream& is, T& x) {
  int v;
  is >> v;
  x = T::raw(v);
  return is;
}

template <class T, atcoder::internal::is_modint_t<T>* = nullptr>
ostream& operator<<(ostream& os, const T& x) {
  return os << x.val();
}

}  // namespace std

namespace linear_sieve {

std::vector<int> primes, lpf;
void init(int n) {
  if (n < int(std::size(lpf))) return;
  if (n < 2 * int(std::size(lpf))) n = 2 * std::size(lpf);
  lpf.resize(n + 1, -1);
  for (int d = 2; d <= n; ++d) {
    if (lpf[d] == -1) lpf[d] = d, primes.push_back(d);
    for (int p : primes) {
      if (p * d > n or p > lpf[d]) break;
      lpf[p * d] = p;
    }
  }
}
std::vector<int> factor(int n) {
  __glibcxx_assert(n >= 1);
  std::vector<int> res;
  for (init(n); n > 1; n /= res.back()) res.push_back(lpf[n]);
  return res;
}

}  // namespace linear_sieve

using namespace std;

#define _ _ [[maybe_unused]]
#define LIFT(f) ([&](auto&&... xs) -> decltype(auto) { return f(forward<decltype(xs)>(xs)...); })
#define Rep(...) [](int l, int r) { return views::iota(min(l, r), r); }(__VA_ARGS__)
#define Rep1(...) [](int l, int r) { return Rep(l, r + 1); }(__VA_ARGS__)
#define Sz(r) int(size(r))
#define IN(...) (cin >> forward_as_tuple(__VA_ARGS__))
#define OUT(...) (cout << forward_as_tuple(__VA_ARGS__) << '\n')

#endif  // __INCLUDE_LEVEL__ == 1
0