为啥开了O2会炸呢????
查看原帖
为啥开了O2会炸呢????
31619
Hzxleo4楼主2020/4/29 21:29

如题,不开 O2O2 能过,开了 O2O2 直接 TT 飞。 求问大佬这是咋回事呀??

代码长这样

#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;
}
2020/4/29 21:29
加载中...