为什么从2开始搞就是错的,从1开始就是对的?
查看原帖
为什么从2开始搞就是错的,从1开始就是对的?
482728
Engulf楼主2023/2/11 12:04

我模板是从2开始的,就能过

WA

LL excrt() {
	LL ans = a[1], M = p[1];
	for (int i = 2; i <= n; i++) {
		LL x, y;
		LL c = (a[i] - (__int128)b[i] * ans % p[i] + p[i]) % p[i];
		LL g = exgcd((__int128)b[i] * M % p[i], p[i], x, y);
		if (c % g) return -1;
		x = (x % p[i] + p[i]) % p[i];
		x = (__int128)x * (c / g) % (p[i] / g);
		ans = ans + (__int128)x * M;
		M = (__int128)M * p[i] / g;
		ans %= M;
	}
	if (ans < mx) ans = ans + (__int128)ceil(mx - ans, M) * M;
	return ans;
}

AC

LL excrt() {
	LL ans = 0, M = 1;
	for (int i = 1; i <= n; i++) {
		LL x, y;
		LL c = (a[i] - (__int128)b[i] * ans % p[i] + p[i]) % p[i];
		LL g = exgcd((__int128)b[i] * M % p[i], p[i], x, y);
		if (c % g) return -1;
		x = (x % p[i] + p[i]) % p[i];
		x = (__int128)x * (c / g) % (p[i] / g);
		ans = ans + (__int128)x * M;
		M = (__int128)M * p[i] / g;
		ans %= M;
	}
	if (ans < mx) ans = ans + (__int128)ceil(mx - ans, M) * M;
	return ans;
}
2023/2/11 12:04
加载中...