#1115945 (C++23) No.3250 最小公倍数

提出ソース
結果

問題	No.3250 最小公倍数
コンテスト
ユーザー	risujiroh
提出日時	2025-08-29 22:15:06
言語	C++23 (gcc 13.3.0 + boost 1.87.0)
結果	TLE
実行時間	-
コード長	15,776 bytes
コンパイル時間	4,798 ms
コンパイル使用メモリ	334,784 KB
実行使用メモリ	247,996 KB
最終ジャッジ日時	2025-10-16 16:20:36
合計ジャッジ時間	26,915 ms
ジャッジサーバーID （参考情報）	judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 1
other	AC * 19 TLE * 3
権限があれば一括ダウンロードができます
ソースコード

raw source code
#if __INCLUDE_LEVEL__ == 0

#include __BASE_FILE__

using Mint = atcoder::modint998244353;

Comb<Mint> comb;

struct D {
  // vector<int> cnt;
  array<int, 20> cnt{};
  int mask = 1;

  void add(int x) {
    // if (x >= Sz(cnt)) {
    //   cnt.resize(x + 1);
    // }
    if (cnt[x]++ == 0) {
      mask |= 1 << x;
    }
  }

  void remove(int x) {
    if (--cnt[x] == 0) {
      mask &= ~(1 << x);
    }
  }

  int get() const {
    return __bit_width(mask) - 1;
  }
};

void Solve() {
  int n;
  IN(n);
  vector<int> a(n);
  IN(a);
  int A = ranges::max(a);
  HldTree g(n);
  for (int _ : Rep(0, n - 1)) {
    int i, j;
    IN(i, j);
    --i, --j;
    g.add_edge({i, j, 1});
  }
  g.build(0);

  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);

  Mint ans = 1;
  vector<D> ds(A + 1);
  vector<int> cnt(A + 1);
  auto add = [&](int x) {
    if (cnt[x]++ == 0) {
      for (auto [p, e] : factors[x]) {
        ans *= comb.Inv(pw[p][ds[p].get()]);
        ds[p].add(e);
        ans *= pw[p][ds[p].get()];
      }
    }
  };
  auto remove = [&](int x) {
    if (--cnt[x] == 0) {
      for (auto [p, e] : factors[x]) {
        ans *= comb.Inv(pw[p][ds[p].get()]);
        ds[p].remove(e);
        ans *= pw[p][ds[p].get()];
      }
    }
  };

  vector<Mint> out(n);
  int L = 0;
  int R = 0;
  for (int i : g.order) {
    int l = g.in[i];
    int r = g.out[i];
    while (L > l) {
      --L;
      add(a[g.order[L]]);
    }
    while (R < r) {
      add(a[g.order[R]]);
      ++R;
    }
    while (L < l) {
      remove(a[g.order[L]]);
      ++L;
    }
    while (R > r) {
      --R;
      remove(a[g.order[R]]);
    }
    out[i] = ans;
  }

  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>
class Comb {
 public:
  Comb() = default;

  explicit Comb(int n) {
    Reserve(n);
  }

  void Reserve(int n) {
    const int sz = static_cast<int>(fact_.size());
    if (n < sz) {
      return;
    }
    fact_.resize(n + 1);
    const int nsz = static_cast<int>(fact_.capacity());
    fact_.resize(nsz);
    fact_inv_.resize(nsz);
    for (int i = sz; i < nsz; ++i) {
      fact_[i] = T(i) * fact_[i - 1];
    }
    fact_inv_.back() = T(1) / fact_.back();
    for (int i = nsz; --i > sz;) {
      fact_inv_[i - 1] = fact_inv_[i] * T(i);
    }
  }

  T Fact(int n) {
    assert(n >= 0);
    Reserve(n);
    return fact_[n];
  }

  T FactInv(int n) {
    if (n < 0) {
      return T(0);
    }
    Reserve(n);
    return fact_inv_[n];
  }

  T FactRatio(int a, int b) {
    if (a >= 0) {
      return Fact(a) * FactInv(b);
    }
    assert(b < 0);
    const T t = FactRatio(~b, ~a);
    return (a - b) % 2 == 0 ? t : -t;
  }

  T Inv(int n) {
    assert(n != 0);
    return FactRatio(n - 1, n);
  }

  T Prod(std::ranges::iota_view<int, int> r) {
    return FactRatio(r.end()[-1], r[-1]);
  }

  T ProdInv(std::ranges::iota_view<int, int> r) {
    assert(r[0] > 0 || r.end()[-1] < 0);
    return FactRatio(r[-1], r.end()[-1]);
  }

  T Perm(int n, int k) {
    assert(n >= 0 ? true : k > n);
    return FactRatio(n, n - k);
  }

  T PermInv(int n, int k) {
    assert(n >= 0 ? k <= n : true);
    return FactRatio(n - k, n);
  }

  T Binom(int n, int k) {
    k = std::max(k, n - k);
    return Perm(n, k) * FactInv(k);
  }

  T BinomInv(int n, int k) {
    assert(n >= 0 ? 0 <= k && k <= n : 0 <= k || k <= n);
    k = std::max(k, n - k);
    return PermInv(n, k) * Fact(k);
  }

  T Multinom(std::span<const int> ks) {
    if (ks.size() < 2) {
      return T(1);
    }
    const int n = std::reduce(ks.begin(), ks.end());
    const int& min_k = *std::ranges::min_element(ks);
    T ret = FactRatio(n, min_k);
    for (const int& k : ks) {
      if (&k != &min_k) {
        ret *= FactInv(k);
      }
    }
    return ret;
  }

  template <class... Ks>
    requires(... && std::same_as<Ks, int>)
  T Multinom(Ks... ks) {
    return Multinom(std::initializer_list<int>{ks...});
  }

  T MultinomInv(std::span<const int> ks) {
    if (ks.size() < 2) {
      return T(1);
    }
    const int n = std::reduce(ks.begin(), ks.end());
    const int& min_k = *std::ranges::min_element(ks);
    assert(n >= 0 ? min_k >= 0
                  : std::ranges::all_of(ks, [&](auto& k) { return &k == &min_k || k >= 0; }));
    T ret = FactRatio(min_k, n);
    for (const int& k : ks) {
      if (&k != &min_k) {
        ret *= Fact(k);
      }
    }
    return ret;
  }

  template <class... Ks>
    requires(... && std::same_as<Ks, int>)
  T MultinomInv(Ks... ks) {
    return MultinomInv(std::initializer_list<int>{ks...});
  }

  T Homogeneous(int n, int k) {
    return Binom(n + k - 1, k);
  }

  T Catalan(int n) {
    assert(n >= 0);
    return Fact(2 * n) * FactInv(n) * FactInv(n + 1);
  }

  T Catalan(int n, int k) {
    assert(0 <= k && k <= n);
    return T(n - k + 1) * Fact(n + k) * FactInv(n + 1) * FactInv(k);
  }

 private:
  std::vector<T> fact_{T(1)};
  std::vector<T> fact_inv_{T(1)};
};

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_;
};

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

struct Graph {
  struct Edge {
    int src, dst;
    int64_t cost;

    int other(int v) const {
      __glibcxx_assert(v == src or v == dst);
      return src ^ dst ^ v;
    }
  };

  std::vector<Edge> edges;
  std::vector<std::vector<std::pair<int, int>>> adj;

  Graph() {}
  explicit Graph(int n) : adj(n) {}

  int n() const { return std::size(adj); }
  int m() const { return std::size(edges); }
  int add_edge(const Edge& e, bool directed) {
    __glibcxx_assert(0 <= e.src and e.src < n());
    __glibcxx_assert(0 <= e.dst and e.dst < n());
    int id = m();
    edges.push_back(e);
    adj[e.src].emplace_back(e.dst, id);
    if (not directed) adj[e.dst].emplace_back(e.src, id);
    return id;
  }
};

struct DfsTree : Graph {
  using T = decltype(Edge::cost);

  std::vector<int> root;
  std::vector<int> pv;
  std::vector<int> pe;
  std::vector<int> order;
  std::vector<int> in;
  std::vector<int> out;
  std::vector<int> sub;
  std::vector<int> depth;
  std::vector<int> min_depth;
  std::vector<T> dist;
  std::vector<int> last;
  int num_trials;

  DfsTree() {}
  explicit DfsTree(int n)
      : Graph(n),
        root(n, -1),
        pv(n, -1),
        pe(n, -1),
        in(n, -1),
        out(n, -1),
        sub(n, -1),
        depth(n, -1),
        min_depth(n, -1),
        dist(n, std::numeric_limits<T>::max()),
        last(n, -1),
        num_trials(0) {}

  int add_edge(const Edge& e) { return Graph::add_edge(e, false); }
  void dfs(int r, bool clear_order = true) {
    __glibcxx_assert(0 <= r and r < n());
    root[r] = r;
    pv[r] = -1;
    pe[r] = -1;
    if (clear_order) order.clear();
    depth[r] = 0;
    dist[r] = T{};
    dfs_impl(r);
    ++num_trials;
  }
  void dfs_all() {
    std::fill(std::begin(root), std::end(root), -1);
    for (int v = 0; v < n(); ++v)
      if (root[v] == -1) dfs(v, v == 0);
  }

  int deeper(int id) const {
    __glibcxx_assert(0 <= id and id < m());
    int a = edges[id].src;
    int b = edges[id].dst;
    return depth[a] < depth[b] ? b : a;
  }
  bool is_tree_edge(int id) const {
    __glibcxx_assert(0 <= id and id < m());
    return id == pe[deeper(id)];
  }
  bool is_ancestor(int u, int v) const {
    __glibcxx_assert(0 <= u and u < n());
    __glibcxx_assert(0 <= v and v < n());
    return in[u] <= in[v] and out[v] <= out[u];
  }

 private:
  void dfs_impl(int v) {
    in[v] = std::size(order);
    order.push_back(v);
    sub[v] = 1;
    min_depth[v] = depth[v];
    last[v] = num_trials;
    for (auto&& [u, id] : adj[v]) {
      if (id == pe[v]) continue;
      if (last[u] == num_trials) {
        min_depth[v] = std::min(min_depth[v], depth[u]);
        continue;
      }
      root[u] = root[v];
      pv[u] = v;
      pe[u] = id;
      depth[u] = depth[v] + 1;
      dist[u] = dist[v] + edges[id].cost;
      dfs_impl(u);
      sub[v] += sub[u];
      min_depth[v] = std::min(min_depth[v], min_depth[u]);
    }
    out[v] = std::size(order);
  }
};

struct HldTree : DfsTree {
  std::vector<int> head;

  HldTree() {}
  explicit HldTree(int n) : DfsTree(n), head(n, -1) {}

  void build(int r, bool clear_order = true) {
    __glibcxx_assert(0 <= r and r < n());
    dfs(r, clear_order);
    order.erase(std::end(order) - sub[r], std::end(order));
    head[r] = r;
    build_impl(r);
  }
  void build_all() {
    std::fill(std::begin(root), std::end(root), -1);
    for (int v = 0; v < n(); ++v)
      if (root[v] == -1) build(v, v == 0);
  }

  int lca(int u, int v) const {
    __glibcxx_assert(0 <= u and u < n());
    __glibcxx_assert(0 <= v and v < n());
    __glibcxx_assert(root[u] == root[v]);
    while (true) {
      if (in[u] > in[v]) std::swap(u, v);
      if (head[u] == head[v]) return u;
      v = pv[head[v]];
    }
  }
  int d(int u, int v) const {
    __glibcxx_assert(0 <= u and u < n());
    __glibcxx_assert(0 <= v and v < n());
    __glibcxx_assert(root[u] == root[v]);
    return depth[u] + depth[v] - 2 * depth[lca(u, v)];
  }
  T distance(int u, int v) const {
    __glibcxx_assert(0 <= u and u < n());
    __glibcxx_assert(0 <= v and v < n());
    __glibcxx_assert(root[u] == root[v]);
    return dist[u] + dist[v] - 2 * dist[lca(u, v)];
  }
  int la(int v, int d) const {
    __glibcxx_assert(0 <= v and v < n());
    __glibcxx_assert(0 <= d and d <= depth[v]);
    while (depth[head[v]] > d) v = pv[head[v]];
    return order[in[head[v]] + (d - depth[head[v]])];
  }
  int next(int src, int dst) const {
    __glibcxx_assert(0 <= src and src < n());
    __glibcxx_assert(0 <= dst and dst < n());
    __glibcxx_assert(root[src] == root[dst]);
    __glibcxx_assert(src != dst);
    if (not is_ancestor(src, dst)) return pv[src];
    return la(dst, depth[src] + 1);
  }
  int next(int src, int dst, int k) const {
    __glibcxx_assert(0 <= src and src < n());
    __glibcxx_assert(0 <= dst and dst < n());
    __glibcxx_assert(root[src] == root[dst]);
    __glibcxx_assert(k >= 0);
    int v = lca(src, dst);
    if (k <= depth[src] - depth[v]) return la(src, depth[src] - k);
    k -= depth[src] - depth[v];
    __glibcxx_assert(k <= depth[dst] - depth[v]);
    return la(dst, depth[v] + k);
  }
  template <class Function> void apply(int src, int dst, bool vertex, Function f) const {
    __glibcxx_assert(0 <= src and src < n());
    __glibcxx_assert(0 <= dst and dst < n());
    __glibcxx_assert(root[src] == root[dst]);
    int v = lca(src, dst);
    while (head[src] != head[v]) {
      f(in[src] + 1, in[head[src]]);
      src = pv[head[src]];
    }
    if (vertex)
      f(in[src] + 1, in[v]);
    else if (src != v)
      f(in[src] + 1, in[v] + 1);
    auto rec = [&](auto self, int to) -> void {
      if (head[v] == head[to]) {
        if (v != to) f(in[v] + 1, in[to] + 1);
        return;
      }
      self(self, pv[head[to]]);
      f(in[head[to]], in[to] + 1);
    };
    rec(rec, dst);
  }
  template <class Searcher> int search(int src, int dst, bool vertex, Searcher f) const {
    __glibcxx_assert(0 <= src and src < n());
    __glibcxx_assert(0 <= dst and dst < n());
    __glibcxx_assert(root[src] == root[dst]);
    int res = -1;
    apply(src, dst, vertex, [&](int l, int r) {
      if (res != -1) return;
      int i = f(l, r);
      if (l > r) std::swap(l, r);
      if (l <= i and i < r) res = vertex ? order[i] : pe[order[i]];
    });
    return res;
  }

 private:
  void build_impl(int v) {
    in[v] = std::size(order);
    order.push_back(v);
    auto pos = std::partition(std::begin(adj[v]), std::end(adj[v]), [&](auto&& e) { return e.second == pe[e.first]; });
    auto it =
        std::max_element(std::begin(adj[v]), pos, [&](auto&& a, auto&& b) { return sub[a.first] < sub[b.first]; });
    if (it != std::begin(adj[v])) std::iter_swap(std::begin(adj[v]), it);
    std::partition(pos, std::end(adj[v]), [&](auto&& e) { return e.second == pe[v]; });
    for (auto&& [u, id] : adj[v]) {
      if (id != pe[u]) break;
      head[u] = u == adj[v].front().first ? head[v] : u;
      build_impl(u);
    }
    out[v] = std::size(order);
  }
};

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 IN(...) (cin >> forward_as_tuple(__VA_ARGS__))
#define OUT(...) (cout << forward_as_tuple(__VA_ARGS__) << '\n')

#endif  // __INCLUDE_LEVEL__ == 1
yukicoder

結果

ソースコード
