用途
解关于 (x) 的线性同余方程组. 形如
[left{
egin{aligned}
x &equiv c_1 pmod{p_1} \
x &equiv c_2 pmod{p_2} \
x &equiv c_3 pmod{p_3} \
& vdots \
x &equiv c_n pmod{p_n} \
end{aligned}
ight.
]
算法过程
主要思路
依次将相邻两个方程合并直到剩余一个方程, 最后的 (c) 即为方程组的一个特解。
具体操作
设现在我们有两个同余方程
[left{
egin{aligned}
x equiv c_1 pmod{p_1} \
x equiv c_2 pmod{p_2} \
end{aligned}
ight.
]
把它们化成不定方程形式, 得
[left{
egin{aligned}
x = k_1 cdot p_1 + c_1 \
x = k_2 cdot p_2 + c_2 \
end{aligned}
ight.
]
联立, 得
[egin{aligned}
k_1 cdot p_1 + c_1 &= k_2 cdot p_2 + c_2 \
&Downarrow \
p_1 cdot k_1 - p_2 cdot k_2 &= c_2-c_1 \
end{aligned}
]
可看作是关于 (k_1,k_2) 的不定方程. 我们可以用 exgcd 求出 (k_1) 的一个特解, 再根据 (x = k_1 cdot p_1 + c_1) 求出 (x) 的一个特解 (sx). (x) 的通解就可以表示为.
[left{
egin{aligned}
x equiv sx pmod{p_1} \
x equiv sx pmod{p_2} \
end{aligned}
ight.
]
这两个式子中, (x) 出现的 "周期" 分别是 (p_1) 和 (p_2), 所以其交集出现的 "周期" 就是 (lcm(p_1,p_2)). 所以 (x) 可以表示为
[x equiv sx pmod{lcm(p_1,p_2)}
]
这样, 我们就成功地合并了两个方程.
按照上述过程, 我们将剩余的方程也依次合并, 最后合并得到的方程的 (c) 即为方程组的一个特解。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
ll n,p1,c1,p2,c2;
ll gi(){
ll x=0; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) x=(x<<3)+(x<<1)+c-'0',c=getchar();
return x;
}
ll Exgcd(ll a,ll b,ll &x0,ll &y0){
if(!b){
x0=1,y0=0;
return a;
}
ll x1,y1,d=Exgcd(b,a%b,x1,y1);
x0=y1;
y0=x1-a/b*y1;
return d;
}
ll Mul(ll a,ll b,ll p){ return ((ull)a*b-(ull)((ld)a/p*b)*p+p)%p; } // 防止溢出
ll Solve(ll a,ll b,ll c){
ll x,y,d=Exgcd(a,b,x,y);
return Mul(c/d,x,b/d);
}
ll Gcd(ll a,ll b){ return !b ?a :Gcd(b,a%b); }
int main(){
n=gi();
p1=gi(),c1=gi();
for(int i=2;i<=n;i++){
p2=gi(),c2=gi();
ll k1=Solve(p1,p2,c2-c1),lcm=p1/Gcd(p1,p2)*p2;
c1=(Mul(k1,p1,lcm)+c1)%lcm,p1=lcm;
}
printf("%lld
",c1);
return 0;
}