class="markdown_views prism-dracula">

参考博客

Acdreamer

---

一次同余方程

a∗x≡b(mod n)" role="presentation">a∗x≡b(mod n)$$a\ast x\equiv b(modn)$$

分情况讨论

---

1. 若有(a,n)=1" role="presentation">(a,n)=1$(a,n)=1$,根据 欧几里得扩展，存在 l,m使得a∗l+n∗m=1" role="presentation">a∗l+n∗m=1$a\ast l+n\ast m=1$，等式两边同时模n，得 a∗l≡1(mod n)" role="presentation">a∗l≡1(mod n)$a\ast l\equiv 1(modn)$,对于 a∗x≡b(mod n)" role="presentation">a∗x≡b(mod n)$$a\ast x\equiv b(modn)$$ a∗l∗x≡b∗l(mod n)" role="presentation">a∗l∗x≡b∗l(mod n)$$a\ast l\ast x\equiv b\ast l(modn)$$x≡b∗l(mod n)" role="presentation">x≡b∗l(mod n)$$x\equiv b\ast l(modn)$$

---

1. 若有 (a,n)=d" role="presentation">(a,n)=d$(a,n)=d$, 对于 a∗x≡b(mod n)" role="presentation">a∗x≡b(mod n)$$a\ast x\equiv b(modn)$$

移项 a∗x−b≡0(mod n)" role="presentation">a∗x−b≡0(mod n)$$a\ast x-b\equiv 0(modn)$$
即 n|(a∗x−b)" role="presentation">n|(a∗x−b)$$n|(a\ast x-b)$$
已知d|a,d|n" role="presentation">d|a,d|n$$d|a,d|n$$
于是 d|b" role="presentation">d|b$$d|b$$
所以同余方程有解的条件是d|b" role="presentation">d|b$d|b$
令 a1=a/d,b1=b/d,n1=n/d" role="presentation">a1=a/d,b1=b/d,n1=n/d$a_1=a/d,b_1=b/d,n_1=n/d$
则有 n1|(a1∗x−b1)" role="presentation">n1|(a1∗x−b1)$$n_1|(a_1\ast x-b_1)$$
即为 a1∗x≡b1(mod n1)     且(a1,n1)=1" role="presentation">a1∗x≡b1(mod n1)     且(a1,n1)=1$$a_1\ast x\equiv b_1(mod{n}_1)且(a_1,n_1)=1$$
就变成情况1，可以解出此时的 x≡b1∗l(mod n1)" role="presentation">x≡b1∗l(mod n1)$$x\equiv b_1\ast l(mod{n}_1)$$
即 x=b1∗l+n1∗t" role="presentation">x=b1∗l+n1∗t$$x=b_1\ast l+n_1\ast t$$t的取值范围 为(0,d-1)

---

中国剩余定理

解线性同余方程，运用拉格朗日插值法，得孙子定理

模板

int m[maxn]; int China(int a[],int n,int b[])//其中a[]是模数，b[] 是余数 { int M = 1; for(int i = 0;i < n;++i) M *= a[i]; int ans = 0; for(int i = 0;i < n;++i) { int Mi = M/a[i]; LL x,y; ex_gcd(Mi,a[i],x,y); ans += b[i] * x*Mi; } ans = (ans%M + M) %M; return ans; }

扩展

合并两个模数
假设
         y=a1(mod m1)" role="presentation">y=