結果
問題 | No.2273 一点乗除区間積 |
ユーザー |
![]() |
提出日時 | 2023-04-14 23:01:48 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 342 ms / 5,000 ms |
コード長 | 1,661 bytes |
コンパイル時間 | 3,530 ms |
コンパイル使用メモリ | 260,456 KB |
実行使用メモリ | 17,408 KB |
最終ジャッジ日時 | 2024-10-10 14:03:04 |
合計ジャッジ時間 | 6,298 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 25 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/modint>#include <atcoder/segtree>using namespace std;map<int, int> factor(int n) {map<int, int> ret;for (int i = 2; i * i <= n; ++i) {while (n % i == 0) {++ret[i];n /= i;}}if (1 < n) {++ret[n];}return ret;}using atcoder::modint;vector<int> ps;struct S {modint r;array<int, 9> e;};S op(S x, S y) {auto e = x.e;for (size_t j = 0; j < size(e); ++j) {e[j] += y.e[j];}return {x.r * y.r, e};}S e() { return {1, {}}; }S makeS(int64_t A) {if (A == 0) {return {0, {}};}auto s = e();for (size_t j = 0; j < size(ps); ++j) {while (A % ps[j] == 0) {++s.e[j];A /= ps[j];}}s.r = A;return s;}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int N, B, Q;cin >> N >> B >> Q;modint::set_mod(B);for (auto [p, e] : factor(B)) {ps.push_back(p);}atcoder::segtree<S, op, e> seg(N);for (int i = 0; i < N; ++i) {int64_t A;cin >> A;seg.set(i, makeS(A));}while (Q--) {int i;int64_t m;int l, r;cin >> i >> m >> l >> r;++r;auto s = makeS(m);if (m == B) {bool multiple = true;auto e = seg.get(i).e;for (size_t j = 0; j < size(ps); ++j) {multiple &= s.e[j] <= e[j];}if (multiple) {for (int& x : s.e) {x = -x;}}}seg.set(i, op(seg.get(i), s));s = seg.prod(l, r);auto ans = s.r;for (size_t j = 0; j < size(ps); ++j) {ans *= modint(ps[j]).pow(s.e[j]);}cout << ans.val() << '\n';}}