新的数论
EXCTR（扩展中国剩余定理）
- 我们知道，中国剩余定理是用来解同余方程组
[left{
egin{aligned}
x ≡ c_1(mod &m_1) \
x ≡ c_2(mod&m_2) \
. \
. \
. \
x ≡ c_r(mod &m_r)
end{aligned}
ight. ]
-
但是有一个非常令人不爽的事情就是它要求(m_1,m_2…,m_r)两两互素
如果某个毒瘤出题人偏要求它们不互素呢？
那就没办法了鸭，只能打死出题人才怪 -
其实也有解决的办法
就是把出题人吊起来干一顿用扩展中国剩余定理（exctr）（敲重点） -
扩展中国剩余定理跟中国剩余定理没半毛钱关系，一个是用扩展欧几里得，一个是用构造
- 首先我们还是从简单入手，考虑一下如果同余方程组只有两个式子的情况
[x≡c_1(mod m_1)$$ $$x≡c_2(mod m_2)
]
将两个式子变形
[x=c_1+m_1k_1$$ $$x=c_2+m_2k_2
]
联立
[c_1+m_1k_1=c_2+m_2k_2
]
移项
[m_1k_1=c_2−c_1+m_2k_2
]
我们用(a,b)表示a,b的最大公约数
在这里需要注意，这个方程有解的条件是((m_1,m_2)|(c_2−c_1))，因为后面会用到(frac {(c_2−c_1)}{(m_2,m_1)})这一项，如果不整除的话肯定会出现小数。
对于上面的方程，两边同除((m_1,m_2))
[frac {m_1k_1}{(m_1,m_2)}=frac {c_2−c_1}{(m_1,m_2)}+frac {m_2k_2}{(m_1,m_2)}$$ $$frac {m_1}{(m_1,m_2)}k_1=frac {c_2−c_1}{(m_1,m_2)}+frac {m_2}{(m_1,m_2)}k_2
]
转换一下
[frac {m_1}{(m_1,m_2)}k_1≡frac {c_2−c_1}{(m_1,m_2)}(mod frac {m_2}{(m_1,m_2)})
]
此时我们已经成功把(k_2)消去了。
同余式两边同除(frac {m_1}{(m_1,m_2)})
[k_1≡inv(frac {m_1}{(m_1,m_2)},frac {m_2}{(m_1,m_2)})∗frac {(c_2−c_1)}{(m_1,m_2)}(mod frac {m_2}{(m_1,m_2)})
]
inv(a,b)表示a在模b意义下的逆元
[k_1=inv(frac {m_1}{(m_1,m_2)},frac {m_2}{(m_1,m_2)})∗frac {(c_2−c_1)}{(m_1,m_2)}+frac {m_2}{(m_1,m_2)}∗y
]
接下来怎么办呢？这个式子已经化到最简了。。。
不要忘了，我们刚开始还有两个式子。我们把(k_1)代回去！
[x=inv(frac {m_1}{(m_1,m_2)},frac {m_2}{(m_1,m_2)})∗frac {(c_2−c_1)}{(m_1,m_2)}∗m_1+yfrac {m_1m_2}{(m_1,m_2)}+c_1$$ $$x≡inv(frac {m_1}{(m_1,m_2)},frac {m_2}{(m_1,m_2)})∗frac {(c_2−c_1)}{(m_1,m_2)}∗m_1+c_1(modfrac {m_1m_2}{(m_1,m_2)})
]
此时，整个式子中的元素我们都已经知道了
具体一点，这个式子可以看做是
[x≡c (mod m)
]
其中
[c=(inv(frac {m_1}{(m_1,m_2)},frac {m_2}{(m_1,m_2)})∗frac {(c_2−c_1)}{(m_1,m_2)})\%frac {m_2}{(m_1,m_2)}∗m_1+c_1$$ $$m=frac {m_1m_2}{(m_1,m_2)}
]
* 推广一下：我们每次把两个同余式合并，求解之后得到一个新的同余式。再把新的同余式和其他的联立，最终就可以求出满足条件的解。