中国剩余定理
中国剩余定理¶
看似要合并 \(n\) 个，实际上可以考虑一个一个添加：
-
无解，后面再怎么加也没有用了
-
先前合并出来的充要条件还是一条同余方程，再合并后仍然是一条同余方程
合并首一¶
先处理两条首一多项式的合并 $$ x = b_i\mod M_i,i=1,2 $$ 等价于 $$ x + M_iy_i= b_i, i=1,2 $$ 同时成立 能推出 $$ M_1y_1 - M_2y_2 = b_1-b_2 $$ 能推出 $$ b_1-b_2 \equiv 0 \mod \gcd(M_1,M_2) $$ 如果不成立直接全局无解。反之，将 \(x\) 根据第一条式子写成 $$ b_1-gM_1'y_1 $$ 考虑怎样的 \(y_1\) 能使第二条式子也成立，实际上和我们前面直接作差的结果差不多，即 $$ gM_1'y_1\equiv (b_1-b_2) \mod gM_2' $$ 约去 \(g\)， $$ M_1'y_1\equiv \frac{b_1-b_2}{g} \bmod M'_2 $$ 这个时候 \(\gcd(M_1',M_2')=1\)，于是 \(M_1'\) 存在 mod \(M_2'\) 意义下的逆元。从而我们得到 \(y_1\) 应该是 mod \(M_2'\) 意义下等于一个定值。继而得到 \(x\) 是模 \(M_1\cdot M_2' = g M_1' M_2'\) 下的一个定值，合并完成。
这个过程虽然动机清晰，但是中间需要精细计算，使用时并不容易记忆。我们给出一个构造性强一点但是简洁一点的算法。
首先构造出满足 \(M_1u + M_2v = g\) 的 \(u,v\)。 验证 \(b_1 + \frac{b_2-b_1}{g}uM_1\) 满足原来两条方程式。 所以前面的都理解了的话，记忆这一条式子就行了，类似斜率表达式的一个东西。\(uM_1\) 就是一个 mod \(M_1\) 为 \(0\) 模 \(M_2\) 为 \(g\) 的类距离项。
首一化¶
尝试把单条可能不是首一的同余方程化为首一的： $$ ax \equiv b \mod M $$ 等价于考虑是否存在整数组 \((x,y)\) s.t. $$ ax + My\equiv b $$ 当且仅当 \(b\) 是 \(\gcd(a,M)\) 的倍数时有解（反之局部无解则全局无解），于是把它们同除以 \(\gcd(a,M)\)，不妨还是保留先前的记号，只不过要记得 \(\gcd(a,M)\) 将等于 \(1\) 了。这个时候 \(a\) 是存在逆元的，用 exgcd 求一下逆元就结束了。
暂时还没用过就先不总结模板了。
练习¶
\(t\) 虽然不确定是不是整数，但是 \(v_xt,v_yt,v_x,x_y\) 是整数。可以先求出 \(v_xv_y t\) which is 整数，再确认 \(v_xt,v_yt\)。
还有一个难点是我们容易把镜像翻转后的斜边理解成一些孤立的线段，导致很难想清楚到底有几条是有交点的。但实际上很多线段之间存在关系：它们在一条直线上。所以只需要考虑两条直线是否相交，至于划分回去属于哪条线段其实并不影响数目上的统计。 然后就是考虑作一条斜率 \(\pm 1\) 的“极限”直线，投影到某一个轴上，可以发现需要统计的直线恰好在一个区间上，转化为统计某个区间内奇整数点的数量。