骗小孩的数论

exgcd

和 同根同源，都是把 转化为 这样的子问题。

考虑求出 的一组特解。

若已知 的一组解 ，则

将 展开成 ，则

整理得

我们不妨令

就结束了。

然而对于一般的不定方程 ，我们可以先考虑解出 的一组解 。

那么原方程的一组解就是 了。

excrt

据说这个比 crt 好理解来着。

excrt 更像是 trick，而非比较牛的算法。

考察同余方程组

我们希望他们被合并成一个。

考虑把他们打开得到

所以有

考虑用 exgcd 解出 的一个可行解 ，我们有

设

则

对 取模可以获得

结束。