题目链接
代码:
/*
扩展中国剩余定理的使用范围更广泛,不要求模数全部互质
扩展中国剩余定理:两两合并同余方程,合并 n - 1 次之后,就能求解
合并两个同余方程:
x ≡ r1 (mod p1) --- x = a*p1 + r1
x ≡ r2 (mod p2) --- x = b*p2 + r2
由上面两式得:x = a*p1 + r1 = b*p2 + r2 --- a*p1 - b*p2 = r2 - r1
根据裴蜀定理,算式 a*p1 - b*p2 = r2 - r1:
当 gcd(p1, p2) | (r2 - r1) 时,有解
通过扩展欧几里得算法可得特解为:
A = X / gcd(p1, p2) * (r2 - r1)
B = Y / gcd(p1, p2) * (r2 - r1)
那么通解就是:
AA = A + p2/gcd(p1, p2) * k
BB = B - p1/gcd(p1, p2) * k
将解代入原方程:
x = AA * p1 + r1
= p1*p2/gcd(p1, p2) * k + p1*A + r1
又变成了 x = a * p + r 的形式
这样合并 n - 1 次,就能得出结果
*/
#include <iostream>
using namespace std;
typedef __int128 LL;
const int N = 1e5 + 10;
int n;
LL p[N], r[N];
inline LL read()
{
LL x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-') f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
inline void print(LL x)
{
if(x < 0)
{
putchar('-');
x = -x;
}
if(x > 9) print(x / 10);
putchar(x % 10 + '0');
}
LL exgcd(LL a, LL b, LL& x, LL& y)
{
if(b == 0)
{
x = 1, y = 0;
return a;
}
LL x1, y1, d;
d = exgcd(b, a % b, x1, y1);
x = y1, y = x1 - a / b * y1;
return d;
}
LL excrt()
{
LL p1 = p[1], r1 = r[1];
for(int i = 2; i <= n; i++)
{
LL p2 = p[i], r2 = r[i];
// 二元一次不定方程:p1 * x + p2 * y = r2 - r1
LL x, y, d, c = r2 - r1;
d = exgcd(p1, p2, x, y);
if(c % d) return -1;
x = c / d * x, y = c / d * y; // 求出特解
// x 有可能是负数,补正一下
LL mod = p2 / d;
x = (x % mod + mod) % mod;
// 求出合并后的 p 和 r,一定要先更新 r,因为会用到 p 的值
r1 = x * p1 + r1;
p1 = p1 / d * p2;
}
return r1 % p1;
}
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i++) p[i] = read(), r[i] = read();
print(excrt());
return 0;
}