中国剩余定理
例题
- 已知以下 n n n同余方程(所有 m i m_i mi互质):
- x ≡ a 1 ( m o d m 1 ) x≡a_1(mod m_1) x≡a1(modm1)
- x ≡ a 2 ( m o d m 2 ) x≡a_2(mod m_2) x≡a2(modm2)
- x ≡ a 3 ( m o d m 3 ) x≡a_3(mod m_3) x≡a3(modm3)
- ……
- x ≡ a n ( m o d m n ) x≡a_n(mod m_n) x≡an(modmn)
- 求最小的 x x x.
样例
n
=
3
n=3
n=3
x
≡
1
(
m
o
d
3
)
x≡1(mod 3)
x≡1(mod3)
x
≡
2
(
m
o
d
5
)
x≡2(mod 5)
x≡2(mod5)
x
≡
3
(
m
o
d
7
)
x≡3(mod 7)
x≡3(mod7)
朴素解法
- 先找出符合第一条的最小的 x x x,
- 那么 x = 4 x=4 x=4.
- 再看使它符合第二条,同时保证第一条成立,每次加上 3 3 3,
- x = 7 x=7 x=7时,成立,
- 还要使它满足第三条,同时保证前两条成立,每次加上 g c d ( 3 , 5 ) = 15 gcd(3,5)=15 gcd(3,5)=15,
- x = 52 x=52 x=52时,成立,
- 所以最终答案就是 x = 52 x=52 x=52。
- 这样做非常慢,如果式子太多效率是非常低的。
中国剩余定理
- 先令 M = Π m i M=Pi{m_i} M=Πmi, c i = M m i c_i=frac{M}{m_i} ci=miM, c i − 1 c_i^{-1} ci−1表示 c i c_i ci在模 m i m_i mi意义下的乘法逆元,
- 则答案 A n s = ∑ a i ∗ c i ∗ c i − 1 m o d M Ans=sum a_i*c_i*c_i^{-1} mod M Ans=∑ai∗ci∗ci−1modM
证明
- 只需要证明方程组中每条式子成立即可,
- 也就是说,证明任意一个 i i i,有 A n s ≡ a i ( m o d m i ) Ans≡a_i(mod m_i) Ans≡ai(modmi)
- 当 i ≠ j i eq j i�=j时,有 c i m o d m j = 0 c_imod m_j=0 cimodmj=0,
- 所以 A n s ≡ ∑ a j ∗ c j ∗ c j − 1 ≡ a i ∗ c i ∗ c i − 1 ≡ a i ( m o d m i ) Ans≡sum a_j*c_j*c_j^{-1} ≡a_i*c_i*c_i^{-1}≡a_i(mod m_i) Ans≡∑aj∗cj∗cj−1≡ai∗ci∗ci−1≡ai(modmi)
- 即该定理成立。
扩展中国剩余定理
例题
- 已知以下 n n n同余方程(所有 m i m_i mi互质的条件不存在了):
- x ≡ a 1 ( m o d m 1 ) x≡a_1(mod m_1) x≡a1(modm1)
- x ≡ a 2 ( m o d m 2 ) x≡a_2(mod m_2) x≡a2(modm2)
- x ≡ a 3 ( m o d m 3 ) x≡a_3(mod m_3) x≡a3(modm3)
- ……
- x ≡ a n ( m o d m n ) x≡a_n(mod m_n) x≡an(modmn)
- 求最小的 x x x.
分析
- 朴素解法仍然适用。
- 但如果用中国剩余定理的话,不保证互质的情况下,乘法逆元无法求得,
- 此时需要用别的方法。
扩展中国剩余定理
- 这里直接用一般的形式来讲解。
- 先使前两条式子成立,
- x ≡ a 1 ( m o d m 1 ) x≡a_1(mod m_1) x≡a1(modm1)
- x ≡ a 2 ( m o d m 2 ) x≡a_2(mod m_2) x≡a2(modm2)
- 可以变形为:
- x = m 1 ∗ y 1 + a 1 x=m_1*y_1+a_1 x=m1∗y1+a1
- x = m 2 ∗ y 2 + a 2 x=m_2*y_2+a_2 x=m2∗y2+a2
- 则 m 1 ∗ y 1 + a 1 = m 2 ∗ y 2 + a 2 m_1*y_1+a_1=m_2*y_2+a_2 m1∗y1+a1=m2∗y2+a2
- 变形得到 m 1 ∗ y 1 − m 2 ∗ y 2 = a 2 − a 1 m_1*y_1-m_2*y_2=a_2-a_1 m1∗y1−m2∗y2=a2−a1
- 式子中的 y 1 y_1 y1和 y 2 y_2 y2是未知的,显然可以用扩展欧几里德来求解!
- 当然要判断 g c d ( m 1 , m 2 ) gcd(m_1,m_2) gcd(m1,m2)是否能被 a 2 − a 1 a_2-a_1 a2−a1整除,如果不行则是无解的。
- 当 y 1 y_1 y1和 y 2 y_2 y2求出以后,都乘上 ( a 2 − a 1 ) / g c d ( m 1 , m 2 ) (a_2-a_1)/gcd(m_1,m_2) (a2−a1)/gcd(m1,m2)
- 求出当前的解 x ′ x' x′.
- 接着当前的解可以转换成一条新的方程式:
- x = x ′ ( m o d l c m ( m 1 , m 2 ) ) x=x'(mod lcm(m_1,m_2)) x=x′(modlcm(m1,m2)),
- 这样继续和下一条方程式合并成一条新的方程式,
- 当只剩一条方程时, x ′ x' x′就是最终的答案。
代码
#include<cstdio>
#include<cstring>
using namespace std;
#define LL long long
LL a[11],m[11];
LL exgcd(LL a,LL b,LL &x,LL &y)
{
if(b==0)
{
x=1;
y=0;
return a;
}
LL d=exgcd(b,a%b,x,y);
LL t=x;
x=y;
y=t-a/b*y;
return d;
}
int main()
{
int n,i;
scanf("%d",&n);
for(i=1;i<=n;i++) scanf("%lld%lld",&m[i],&a[i]);
LL A=a[1],M=m[1];
for(i=2;i<=n;i++)
{
LL x=0,y=0;
LL l=a[i]-A;
LL d=exgcd(M,m[i],x,y);
if(l%d>0)
{
printf("-1");
return 0;
}
x*=l/d;
x=(x%m[i]+m[i])%m[i];
A+=M*x;
M=M/d*m[i];
A%=M;
}
printf("%lld",A);
return 0;
}