求解线性同余方程组的一种方法
首先考虑前两个线性同余方程:
$$
x \equiv a_1 \mod p_1\\
$$
$$
x \equiv a_2 \mod p_2\\
$$
分别可以写成:
$$
x = p_1 \cdot k_1 + a_1\\
$$
$$
x = p_2 \cdot k_2 + a_2\\
$$
将这两个方程合并移项,可得:
$$
p_1 \cdot k_1 - p_2 \cdot k_2 = a_2 - a_1
$$
暂且把负号吸收到 $k_2$ 中,得:
$$
p_1 \cdot k_1 + p_2 \cdot k_2 = a_2 - a_1
$$
将 $k_1,k_2$看做这个等式的变量,并用贝祖定理 + 扩展欧几里得算法来判断是否有解。如果有解,则继续往下走。
通过扩展欧几里得算法算出 $d=(p_1,p_2)$
此时我们可以求出 $k_1$ 的通解:
$$
k_1’ = k_1 \cdot \frac{a_2 - a_1}{d} + \frac{p_2}{d} \cdot k,k\in Z
$$
将 $k_1’$ 代入 $k_1$
$$
x = p_1 \cdot k_1 + a_1
$$
得:
$$
x = (k_1 \cdot \frac{a_2 - a_1}{d} + \frac{p_2}{d} \cdot k) \cdot p1 + a_1
$$
整理得:
$$
x = \frac{p_1 p_2}{d} \cdot k + a_1 + k_1 \cdot \frac{a_2 - a_1}{d} \cdot p_1
$$
可以发现这个方程形似上述的方程
$$
x=p \cdot k + a
$$
这时候可以对比各数:
$$
p = \frac{p_1p_2}{d}\\
$$
$$
a = a_1 + k_1 \cdot a_1 \cdot \frac{a_2 - a_1}{d}
$$
将得到的方程与下一个方程继续合并直到只剩下一个方程:
$$
x = p \cdot k + a\\
$$
$$
x = p_3 \cdot k_3 + a_3\\
$$
$$
\vdots
$$
得到最后的方程:
$$
x = p’ \cdot k’ + a’
$$
因为要求最小非负整数解,故:
$$
x = a’ \mod p’
$$
代码
ll solve(vector<int> a, vector<int> p){
int n = a.size();
ll p1 = p[0], a1 = a[0];
for (int i = 1; i < n; i ++ ){
ll p2 = p[i], a2 = a[i], k1, k2;
ll d = exgcd(p1, p2, k1, k2);
if ((a2 - a1) % d)
return -1;
k1 *= (a2 - a1) / d;
k1 = mod(k1, p2 / d);
a1 += k1 * p1;
p1 *= p2 / d;
}
return mod(a1, p1);
}
完整代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod(ll a, ll b){
return (a % b + b) % b;
}
ll exgcd(ll a, ll b, ll &x, ll &y){
if (!b){
x = 1, y = 0;
return a;
}
ll d = exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
ll solve(vector<int> a, vector<int> p){
int n = a.size();
ll p1 = p[0], a1 = a[0];
for (int i = 1; i < n; i ++ ){
ll p2 = p[i], a2 = a[i], k1, k2;
ll d = exgcd(p1, p2, k1, k2);
if ((a2 - a1) % d)
return -1;
k1 *= (a2 - a1) / d;
k1 = mod(k1, p2 / d);
a1 += k1 * p1;
p1 *= p2 / d;
}
return mod(a1, p1);
}
int main(){
int n;
cin >> n;
vector<int> p, a;
for (int i = 0; i < n; i ++ ){
int px, ax;
cin >> px >> ax;
p.push_back(px);
a.push_back(ax);
}
cout << solve(a, p);
return 0;
}
x=p1p2d⋅k+a1+k1⋅a2−a1d⋅a1 这个写错了把 最后应该是 ${\cdot p_1}$
感谢指正