結果

問題 No.3026 Range LCM (Online Version)
ユーザー とりゐ
提出日時 2025-02-14 23:18:30
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 4,113 bytes
コンパイル時間 3,563 ms
コンパイル使用メモリ 295,636 KB
実行使用メモリ 773,684 KB
最終ジャッジ日時 2025-02-14 23:27:57
合計ジャッジ時間 184,770 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 2 TLE * 4 MLE * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

#define ll long long
#define elif else if
#define vi vector<int>
#define vll vector<ll>
#define vvi vector<vi>
#define pii pair<int, int>

#define repname(a, b, c, d, e, ...) e
#define rep(...) repname(__VA_ARGS__, rep3, rep2, rep1, rep0)(__VA_ARGS__)
#define rep0(x) for (int rep_counter = 0; rep_counter < (x); ++rep_counter)
#define rep1(i, x) for (int i = 0; i < (x); ++i)
#define rep2(i, l, r) for (int i = (l); i < (r); ++i)
#define rep3(i, l, r, c) for (int i = (l); i < (r); i += (c))

struct ScalarInput
{
  template <class T>
  operator T()
  {
    T ret;
    cin >> ret;
    return ret;
  }
};
struct VectorInput
{
  size_t n;
  VectorInput(size_t n) : n(n) {}
  template <class T>
  operator vector<T>()
  {
    vector<T> ret(n);
    for (T &x : ret)
      cin >> x;
    return ret;
  }
};
ScalarInput input() { return ScalarInput(); }
VectorInput input(size_t n) { return VectorInput(n); }

template <typename T>
void print(vector<T> a)
{
  for (int i = 0; i < a.size(); i++)
  {
    cout << a[i] << " \n"[i + 1 == a.size()];
  }
}

template <class T>
void print(T x)
{
  cout << x << '\n';
}

template <class Head, class... Tail>
void print(Head &&head, Tail &&...tail)
{
  cout << head << ' ';
  print(forward<Tail>(tail)...);
}

#include <atcoder/segtree>
#include <atcoder/modint>
using namespace atcoder;
using mint = modint998244353;

mint op(mint a, mint b) { return a * b; }
mint e() { return 1; }

int op_max(int a, int b) { return max(a, b); }
int e_max() { return 0; }
int M = 200010;
int B = 448;
int K = 800;
vi seive(M, -1);
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  vi smallp, smallp_idx(B);
  int tmp = 0;
  for (int i = 2; i < M; i++)
  {
    if (seive[i] == -1)
    {
      for (int j = i; j < M; j += i)
      {
        seive[j] = i;
      }
      if (i < B)
      {
        smallp.push_back(i);
        smallp_idx[i] = tmp;
        tmp++;
      }
    }
  }

  int N, Q;
  cin >> N;
  vi A(N);
  rep(i, N) cin >> A[i];
  vvi small_table(tmp, vi(N, 0));
  vi bigp(N, -1);
  rep(i, N)
  {
    while (A[i] > 1)
    {
      int p = seive[A[i]];
      int c = 0;
      while (A[i] % p == 0)
      {
        c++;
        A[i] /= p;
      }
      if (p >= B)
        bigp[i] = p;
      else
      {
        small_table[smallp_idx[p]][i] = c;
      }
    }
  }
  vector<segtree<int, op_max, e_max>> seg1;
  rep(i, tmp)
  {
    seg1.push_back(segtree<int, op_max, e_max>(small_table[i]));
  }

  vi nxt(N, N);
  vector<segtree<mint, op, e>> seg2;
  {
    vi memo(M, N);
    for (int i = N - 1; i >= 0; i--)
    {
      if (bigp[i] != -1)
      {
        nxt[i] = memo[bigp[i]];
        memo[bigp[i]] = i;
      }
    }
    segtree<mint, op, e> seg0(N);
    rep(i, M)
    {
      if (memo[i] != N)
      {
        seg0.set(memo[i], i);
      }
    }
    rep(l, N)
    {
      if (l % K == 0)
        seg2.push_back(seg0);
      if (bigp[l] != -1)
      {
        seg0.set(l, 1);
        if (nxt[l] != N)
          seg0.set(nxt[l], bigp[l]);
      }
    }
  }

  cin >> Q;
  mint ans = 1;
  vi used(M, -1);
  rep(qi, Q)
  {
    ll x, y;
    cin >> x >> y;
    ll l = mint(ans * mint(x)).val(), r = mint(ans * mint(y)).val();
    l %= N;
    r %= N;
    if (l > r)
      swap(l, r);
    r++;
    mint nans = 1;
    rep(i, tmp)
    {
      int mx = seg1[i].prod(l, r);
      rep(j, mx) nans *= smallp[i];
    }

    int LK = ((l + K - 1) / K) * K;
    int RK = ((r + K - 1) / K) * K;
    if (LK == RK)
    {
      rep(j, l, r)
      {
        if (bigp[j] != -1)
        {
          int p = bigp[j];
          if (used[p] != qi)
          {
            used[p] = qi;
            nans *= bigp[j];
          }
        }
      }
    }
    else
    {
      nans *= seg2[LK / B].prod(LK, r);
      int nowL = LK;
      while (nowL != l)
      {
        nowL--;
        if (bigp[nowL] != -1)
        {
          int p = bigp[nowL];
          if (nxt[nowL] >= r && used[p] != qi)
          {
            nans *= p;
            used[p] = qi;
          }
        }
      }
    }
    cout << nans.val() << endl;
    ans = nans;
  }
}
0