口胡了一下 $\mathrm{CRT}$ 和 $\mathrm{exCRT}$
Tips
- 代码是自己YY的，没有写过题，不保证正确性或细节正确。
- $\mathrm{inv}(a,p)$ 表示 $a$ 在模 $p$ 意义下的逆元。
- $\mathrm{gcd}(a,b)$ 表示 $a$ 和 $b$ 的最大公约数。
- 感觉会有细节处理不好，欢迎指错。
中国剩余定理
中国剩余定理 $\mathrm{(Chinese\;remainder\;theorem(CRT))}$ 是用来求解一元线性同余方程组的一个东西。
具体来说是解这样的同余方程组：
\[\left\{ \begin{array}{c} x\equiv a_1\pmod {m_1}\\ x\equiv a_2\pmod {m_2} \\ x\equiv a_3\pmod {m_3}\\ \cdots \\ x\equiv a_k\pmod {m_k} \end{array} \right.\]并且满足 $\forall 1\leq i\not= j\leq k,\mathrm{gcd}(m_1,m_2)=1 \tag1$
中国剩余定理可以求出这个同余方程组的最小非负整数解。
令 $M=\prod\limits_{i=1}^{k}m_i$，那么方程模 $M$ 意义下的唯一解是 \(x=(\sum\limits_{i=1}^{k}a_i*{\frac{M}{m_i}}*\mathrm{inv}({\frac{M}{m_i}},m_i))\% M\)
证明不存在的，记住结论就好了。
代码好像很好写的样子。
ll CRT(ll *a,ll *m,int k) {
ll M=1;
for(int i=1;i<=k;i++) M*=m[i];
ll ans=0;
for(int i=1;i<=k;i++)
ans=(ans+a[i]*(M/m[i])*inv(M/m[i],m[i])%M;
return ans;
}
逆元应该很好求吧，随便什么exgcd，费马小定理搞一搞就好了。
扩展中国剩余定理
扩展中国剩余定理可以求解不满足限制条件 $1$ 的同余方程组。
考虑合并两个方程
\[\left\{ \begin{array}{c} x\equiv a_1\pmod {m_1}\\ x\equiv a_2\pmod {m_2} \end{array} \right.\]$``\equiv”$ 这个符号比较讨厌，我们换一下形式，写成
\[\left\{ \begin{array}{c} x=k_1m_1+a_1\\ x=k_2m_2+a_2 \end{array} \right.\]那就有
\[\begin{aligned}k_1m_1+a_1=&k_2m_2+a_2\\k_1m_1-k_2m_2=&a_2-a_1\end{aligned}\]这个是符合 $ax+by=c$这个形式的，
那根据 裴蜀定理 我们可以知道方程有解的条件为 $\mathrm{gcd}(m_1,m_2)\mid (a_2-a_1)$
假设这个方程有解，方程两边同时除以 $\mathrm{gcd}(m_1,m_2)$ 得到
\[\begin{aligned}\frac{k_1m_1}{\mathrm{gcd}(m_1,m_2)}-\frac{k_2m_2}{\mathrm{gcd}(m_1,m_2)}=\frac{a_2-a_1}{\mathrm{gcd}(m_1,m_2)}\end{aligned}\]$k_1,k_2$ 都是不确定的一个数，我们把他们从分子上拆下来，得到
\[\begin{aligned}k_1\frac{m_1}{\mathrm{gcd}(m_1,m_2)}-k_2\frac{m_2}{\mathrm{gcd}(m_1,m_2)}=\frac{a_2-a_1}{\mathrm{gcd}(m_1,m_2)}\\\\k_1\frac{m_1}{\mathrm{gcd}(m_1,m_2)}=\frac{a_2-a_1}{\mathrm{gcd}(m_1,m_2)}+k_2\frac{m_2}{\mathrm{gcd}(m_1,m_2)}\end{aligned}\]我们设
\[\left\{ \begin{array}{c} x' &=& k_1\frac{m_1}{\mathrm{gcd}(m_1,m_2)}\\ a' &=& \frac{a_2-a_1}{\mathrm{gcd}(m_1,m_2)}\\ k' &=& k_2 \\ m' &=& \frac{m_2}{\mathrm{gcd}(m_1,m_2)} \end{array} \right.\]然后刚才那个式子就可以写成 $x’=k’m’+a’$，那就可以写成 $x’\equiv a’\pmod{m’} $
再把 $x’,a’,m’$ 换回去得到
\[k_1\frac{m_1}{\mathrm{gcd}(m_1,m_2)}\equiv \frac{a_2-a_1}{\mathrm{gcd}(m_1,m_2)}\pmod {\frac{m_2}{\mathrm{gcd}(m_1,m_2)}}\]方程两边同时除以 $\Large\frac{m_1}{\mathrm{gcd}(m_1,m_2)}$ 得到
\[k_1\equiv \mathrm{inv}(\frac{m_1}{\mathrm{gcd}(m_1,m_2)},\frac{m_2}{\mathrm{gcd}(m_1,m_2)})*\frac{a_2-a_1}{\mathrm{gcd}(m_1,m_2)} \pmod{\frac{m_2}{\mathrm{gcd}(m_1,m_2)}}\]$``\equiv”$ 这个符号比较讨厌，我们换一下形式，写成
\[k_1=k\frac{m_2}{\mathrm{gcd}(m_1,m_2)}+\mathrm{inv}(\frac{m_1}{\mathrm{gcd}(m_1,m_2)},\frac{m_2}{\mathrm{gcd}(m_1,m_2)})*\frac{a_2-a_1}{\mathrm{gcd}(m_1,m_2)}\]再把 $k_1$ 代入到 $x=k_1m_1+a_1$ 中，我们就会得到一个巨长的式子
\[\\\\\begin{aligned}x&=m_1(k\frac{m_2}{\mathrm{gcd}(m_1,m_2)}+\mathrm{inv}(\frac{m_1}{\mathrm{gcd}(m_1,m_2)},\frac{m_2}{\mathrm{gcd}(m_1,m_2)})*\frac{a_2-a_1}{\mathrm{gcd}(m_1,m_2)})+a_1\\\\\\x&=k\frac{m_1m_2}{\mathrm{gcd}(m_1,m_2)}+m_1*\mathrm{inv}(\frac{m_1}{\mathrm{gcd}(m_1,m_2)},\frac{m_2}{\mathrm{gcd}(m_1,m_2)})*\frac{a_2-a_1}{\mathrm{gcd}(m_1,m_2)})+a_1\end{aligned}\]然后我们设
\[\left\{ \begin{array}{c} m' &=& \frac{m_1m_2}{\mathrm{gcd}(m_1,m_2)}\\\\ a' &=& m_1*\mathrm{inv}(\frac{m_1}{\mathrm{gcd}(m_1,m_2)},\frac{m_2}{\mathrm{gcd}(m_1,m_2)})*\frac{a_2-a_1}{\mathrm{gcd}(m_1,m_2)})+a_1 \end{array} \right.\]发现上面那个巨长的式子可以写成 $x=km’+a’$，那就可以写成 $x\equiv a’\pmod{m’}$
现在我们历尽千辛万苦终于把
合并成了 $x\equiv a’\pmod{m’}$
这个式子又可以和其他的合并，然后就可以一直合并下去了。
显然会合并 $k-1$ 次，最后得到一个同余方程 $x\equiv a\pmod m$
然后再套用一下 exgcd 解同余方程就好了。
好吧，我sb了。最后答案就是 $(a\%m+m)\%m$
代码也挺简单的。
ll exCRT(ll *a,ll *m,int k) {
ll a1=a[1],a2=a[2],m1=m[1],m2=m[2];
for(int i=1,j=3;i<k;i++,j++) {
ll g=gcd(m1,m2);
if((a2-a1)%g) return -1;
ll mm=m1/g*m2,aa=m1*inv(m1/g,m2/g)*((a2-a1)/g)+a1;
a1=aa,a2=a[j],m1=mm,m2=m[j];
}
return (a1%m1+m1)%m1;
}
坑
-
$\mathrm{CRT}$ 的证明。
应该是不会填的。 -
代码的正确性。
-
细节的处理。