如题,不开 O2 能过,开了 O2 直接 T 飞。 求问大佬这是咋回事呀??
#include <bits/stdc++.h>
#define N 100005
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
LL z = 1;
LL read(){
LL x, f = 1;
char ch;
while(ch = getchar(), ch < '0' || ch > '9') if(ch == '-') f = -1;
x = ch - '0';
while(ch = getchar(), ch >= '0' && ch <= '9') x = x * 10 + ch - 48;
return x * f;
}
int ksm(int a, int b, int p){
int s = 1;
while(b){
if(b & 1) s = z * s * a % p;
a = z * a * a % p;
b >>= 1;
}
return s;
}
LL exgcd(LL a, LL b, LL &x, LL &y){
if(!b) x = 1, y = 0;
else{
exgcd(b, a % b, y, x);
y -= a / b * x;
}
}
LL excrt(int n, LL *a, LL *b){
LL x, B, M, t, k, g;
__int128 z = 1;
x = a[1], B = b[1];
for(int i = 2; i <= n; i++){
g = __gcd(B, b[i]);
M = B / g * b[i];
if((a[i] - x) % g != 0) return -1;
exgcd(B / g, b[i] / g, t, k);
t = (z * t * (a[i] - x) / g % M + M) % M;
x = (x + z * t * B % M) % M;
B = M;
}
return x;
}
LL a[N], b[N];
int main(){
int i, j, n, m;
n = read();
for(i = 1; i <= n; i++) b[i] = read(), a[i] = read();
printf("%lld", excrt(n, a, b));
return 0;
}