实际上是同余方程组的合并

简述

如果给定$n$个同余方程组
$$
\begin{cases}
x &\equiv b_1 \pmod {a_1} \\
x &\equiv b_2 \pmod {a_2} \\
x &\equiv b_3 \pmod {a_3} \\
&\cdots \\
x &\equiv b_n \pmod {a_n} \\
\end{cases}
$$
保证$a$是正整数,$b$是非负整数

现在要求找一个非负整数$x$,使得$x$最小且满足这$n$同余方程

数据保证$x$不超过$10^{18}$

题解

现在考虑合并两个同余方程的时候该怎么做
$$
\begin{cases}
x \equiv b \pmod {a} \\
x \equiv B \pmod {A}
\end{cases}
$$
这个可以写作
$$
\begin{cases}
x = ay + b \\
x = AY + B
\end{cases}
$$
由于$x$是一个常量,因此$ay+b=AY+B$,其中$a,b,A,B$都是常数

整理一下后就是$ay+A(-Y)=B-b$

通过$exgcd$,可以获得一组关于$ay+A(-Y)=\gcd(a,A)$的解$(y_0,-Y_0)$

即$a(y_0 \times \frac{B-b}{\gcd(a,A)})+A(-Y_0 \times \frac{B-b}{\gcd(a,A)})=\gcd(a,A) \times \frac{B-b}{\gcd(a,A)}=B-b$

由于$x=ay+b$,现在要最小化$x$,也就是最小化$y$,即最小化$t=y_0 \times \frac{B-b}{\gcd(a,A)}$

由于$t$的通解为$t+\frac{A}{\gcd(a,A)}k$,因此$t$的最小值为$t_0=t \bmod \frac{A}{\gcd(a,A)}$

于是就可以将这两个同余方程合并为
$$
x \equiv a \times t_0+b \pmod {\mathbb{lcm}(a,A)}
$$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>
using namespace std;
typedef __int128 ll;
const int N = 1e5 + 10;
ll x, y, d; int n;

void exgcd(ll &x, ll &y, ll a, ll b) {
if(!b) d = a, x = 1, y = 0;
else exgcd(y, x, b, a % b), y -= a / b * x;
}

ll gcd(ll a, ll b) {
return b ? gcd(b, a % b) : a;
}

ll lcm(ll a, ll b) {
return a / gcd(a, b) * b;
}

ll a, b, A, B;

void merge() {
exgcd(x, y, a, A);
ll c = B - b;
if(c % d) puts("-1"), exit(0);
x = x * c / d % (A / d);
if(x < 0) x += A / d;
ll mod = lcm(a, A);
b = (a * x + b) % mod; if(b < 0) b += mod;
a = mod;
}

int main() {
scanf("%d", &n);
for(int i = 1 ; i <= n ; ++ i) {
long long _A, _B;
scanf("%lld%lld", &_A, &_B), A = _A, B = _B;
if(i > 1) merge();
else a = A, b = B;
}
printf("%lld\n", (long long)(b % a));
}