提出 00c2f78b-d535-4efb-a19f-721044c08b50

コード

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

using i128 = __int128_t;

static inline i128 im(i128 a, i128 m){
i128 r = a % m;
if (r < 0) r += m;
return r;
}
static i128 ex(i128 a, i128 b, i128 &x, i128 &y){
if (b == 0){
x = 1; y = 0;
return a >= 0 ? a : -a;
}
i128 x1, y1;
i128 g = ex(b, a % b, x1, y1);
x = y1;
y = x1 - (a / b) * y1;
return g;
}
static inline i128 ig(i128 a, i128 b){
if (a < 0) a = -a;
if (b < 0) b = -b;
while (b){
i128 t = a % b;
a = b; b = t;
}
return a;
}
static inline i128 mo(i128 a, i128 mod){
i128 x, y; ex(a, mod, x, y);
return im(x, mod);
}

struct C {
bool ok;
i128 r, m;
C(bool ok=false, i128 r=0, i128 m=1): ok(ok), r(r), m(m) {}
};

static C me(const C &A, const C &B){
if (!A.ok || !B.ok) return C(false, 0, 1);
i128 r1 = A.r, m1 = A.m;
i128 r2 = B.r, m2 = B.m;
if (m1 == 0 || m2 == 0) return C(false, 0, 1);

i128 g = ig(m1, m2);
i128 k = r2 - r1;
if (k % g != 0) return C(false, 0, 1);

i128 m1g = m1 / g;
i128 m2g = m2 / g;
i128 inv = mo(im(m1g, m2g), m2g);
i128 t = im((k/g) * inv, m2g);

i128 r = r1 + m1 * t;
i128 lcm = m1 * m2g;
r = im(r, lcm);
return C(true, r, lcm);
}

int main(){

int N;
if (!(cin >> N)) return 0;

vector<long long> a(N), b(N);
for (int i = 0; i < N; i++){
cin >> a[i] >> b[i];
}

int LO = 1;
while ((1<<LO) <= N) ++LO;

vector<vector<C>> dp(LO, vector<C>(N));

for (int i = 0; i < N; i++){
if (b[i] <= 0){
dp[0][i] = C(false, 0, 1);
} else {
i128 m = (i128)b[i];
i128 r = im((i128)a[i], m);
dp[0][i] = C(true, r, m);
}
}

for (int k = 1; k < LO; k++){
int len = 1<<(k-1);
for (int i = 0; i < N; i++){
if (i + len >= N){
dp[k][i] = dp[k-1][i];
} else {
dp[k][i] = me(dp[k-1][i], dp[k-1][i+len]);
}
}
}

int Q; cin >> Q;
const long long LIM = (1LL<<31) - 1;

while (Q--){
int L, R;
cin >> L >> R;
--L;
C acc(true, 0, 1);
int pos = L;
for (int k = LO-1; k >= 0; k--){
int len = 1<<k;
if (pos + len <= R){
acc = me(acc, dp[k][pos]);
pos += len;
if (!acc.ok) break;
}
}

if (!acc.ok){
cout << -1 << endl;
continue;
}

 if (acc.r == 0){
    if (acc.m > (i128)LIM){ cout << -1 << endl; continue; }
    cout << (long long)acc.m << endl;
    continue;
 }

if (acc.r > (i128)LIM){
cout << -1 << endl;
} else {
cout << (long long)acc.r << endl;
}
}
}
結果

問題	点数	言語	結果	実行時間	メモリ
I. Segment CRT	150	C++ (gcc)	AC	482 ms	89084 KiB