結果

問題 No.3026 Range LCM (Online Version)
コンテスト
ユーザー とりゐ
提出日時 2025-02-14 23:32:16
言語 C++23
(gcc 13.3.0 + boost 1.89.0)
結果
RE  
実行時間 -
コード長 4,171 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,743 ms
コンパイル使用メモリ 293,968 KB
実行使用メモリ 408,940 KB
最終ジャッジ日時 2025-02-14 23:34:18
合計ジャッジ時間 90,527 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge7
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 10 RE * 8 TLE * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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


int op_max(int a, int b) { return max(a, b); }
int e_max() { return 0; }
int M = 200010;
int B = 448;
int K = 1000;
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<vector<mint>>big_table;
  {
    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;
      }
    }
    vector<mint>res(N,1);
    rep(i, M)
    {
      if (memo[i] != N)
      {
        res[memo[i]]=i;
      }
    }

    rep(l, N)
    {
      if (l % K == 0){
        vector<mint>res1(N,1);
        mint prod=1;
        rep(i,N){
          prod*=res[i];
          res1[i]=prod;
        }
        big_table.push_back(res1);
      }
      if (bigp[l] != -1)
      {
        res[l]=1;
        if (nxt[l] != N){
          res[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 *= big_table[LK / B][r-1];
      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