竞赛程序答案常在定理与输入条件的交界出错。模除法需要可能不存在的逆元;叉积为零时须另检查重叠。两个题目共享一个好习惯:先把判断化成精确不变量,再明确处理例外。
除法前先解同余
定义 17.1.1
(线性同余)
对整数 和正整数 , 表示某整数 满足 。记 。
定理 17.1.2
(线性同余的可解性)
设 为整数, 为正整数,。同余式 有解,当且仅当 。此时它的解恰好构成模 的一个剩余类,相当于模 的恰好 个不同剩余类。
证明
(以最大公因数化简)
若有解, 同时整除 和 ,所以 。反之,设 ,把 除以 :化简后的同余式 ,其系数与模数互素,所以 Bézout 恒等式给出 的模 逆元 ,以及解 。原同余式的每个解经此除法都满足化简后的同余式,而化简后同余式的每个解乘以 即满足原同余式。所以解恰好是模 的一个剩余类,而这个类分成模 的 个剩余类。
证明透视
为什么可以约去最大公因数,却不能约去系数
证明除以的是 ,而不是 。除了之后,系数 与模数 互素,这正是 Bézout 恒等式产生逆元所需的条件。除法同时也把模数除以 :同余式只能连同模数一起除以 。所以解集是模 的一个类,而不是模 的类,并且模 出现 个剩余类。当 时,论证就是普通的逆元。必要性只用到 同时整除 和 ,完全不需要逆元。
这不等于在模 时随意约去 。 的模 逆元存在当且仅当 。例如 2 没有模 6 逆元:任何剩余类乘 2 都得偶剩余类。同余式仍可能有解,例如 。Fermat 公式 要求 是素数且 ;模数为合数或 是 倍数时,该理由失效。
反例模式
约去公因数时模数也要改变
声称: 推出 。取 、。则 、,假设成立,但 不能被 整除。修正方法是把 连同模数一起约去:,即 ,而 确实成立。同理, 的解为 ,即模 的两个剩余类 与 ;验算 。
常见错误
(对合数模数使用 Fermat 逆元公式)
取 、,公式 给出 ,但 。 模 的逆元是 ,因为 。指数 只在模数 为素数且 时才有根据。
例题:系数不可逆
例题 17.1.3
(系数不可逆的同余式)
解 。 且 ,故有解。除以 2 得 。Euclid 给出 ,故 ,。因此 ;模 100 的两个剩余类为 和 。直接核对 、。若右边是 31,最大公因数不整除它,便无解。
扩展 Euclid 不只求最大公因数,也构造系数。一般算法不断把 换成 ,直至余数为零;回代维持整数线性组合。正模数下应把负逆元归一化为所需的非负代表。程序语言的余数惯例不同,不要假设 -7 % 50 必定是 43,须明确处理。
概念视角结构
解集是子群的一个陪集
在加法群 中,满足 的剩余类 构成子群 。因为 恰在 整除 时成立,所以 ,阶为 。若 是 的一个解,则全部解集就是陪集 。例如 中,,,解为 和 。映射 的像是 的倍数构成的子群,所以 必须落在其中。
定向使用正负号而非斜率
定义 17.1.4
(三点的定向)
对平面点定义
正值表示由有向 转向 是左转,负值是右转,零表示共线;不用除以水平或垂直坐标差。对两条非退化闭线段 、,若 C、D 相对 AB 的定向值严格异号,且 A、B 相对 CD 的定向值也严格异号,便是内部真正相交。若某个定向值为零,须检查该点是否在另一线段的坐标包围盒内。单靠共线不能判断线段是否重叠。
例题:交叉与重叠
例题 17.1.5
(相交、重叠与分离的线段)
取 、、、。C、D 相对 AB 的定向值为 、;A、B 相对 CD 的为 、。两对均严格异号,故线段真正相交。参数式 与 给出 ,唯一交点是 。
保留 A、B,但改用 、。四个定向值皆为零,因各点在 上; 区间 与 重叠于 ,所以闭线段共有从 到 的整段,而非仅一个点。若第二线段改为从 到 ,仍共线,但包围盒不相交,故线段不相交。
两端点相同的点线段应作点在线段上的测试,不能只依赖“真正交叉”论证。坐标为整数时,要用足够宽的整数类型计算两个乘积及其差。即使单一乘积能放下,相减仍可能溢出;须由坐标限制及表示方式推导界,不能用浮点斜率代替溢出证明。算术溢出后,原本正确的符号测试也不再正确。
常见错误
(零定向值不表示重叠)
叉积为零只说明三点共线。对 、、、,四个定向值都是零,但 与 不相交,因为它们的 区间 与 没有公共部分。定向值为零之后,必须检查包围盒。
检查整个化约
同余证明有必要性及充分性;只报 而不构造缩减后的逆元,便缺了一半论证。线段测试也有两层:严格异号处理真正交叉;出现零值时须检查端点和重叠。先测普通实例,再刻意测共用端点、平行重叠和分离的共线线段。这些情况往往能暴露随机外观输入未触及的假设。
合并同余时不要假设互素
熟悉的中国剩余定理在模数 互素时,给出模 的一个剩余类。若它们有公因数,须先检查相容性。
定理 17.1.6
(两个同余式的相容性)
设 为正整数,。方程组 、 有解,当且仅当 。此时所有解恰好构成模 的一个剩余类,不一定是模 。
证明
(必要性靠相减,充分性靠解同余式)
若 ,则 可被 整除。反之,设 。同余式 的右边被 整除,由上面的可解性定理它有解 ;于是 同时满足两个同余式。若 与 是两个解, 同时被 与 整除,所以被 整除;而在解上加最小公倍数的倍数,两个同余式仍然成立。所以解构成模最小公倍数的一个类。
例题:相容与不相容的余数
例题 17.1.7
(相容与不相容的余数)
解 、。最大公因数是 2,整除差 ,故相容。写 ,第二条变为 ,等价于 。由 ,得 ,故 ;19 的余数确为 1 和 3。相反,、 无解,因差 1 不被 2 整除。把不相容同余当作互素情况合并,可能得到看似合理但无法通过原式核对的整数。
实现须一致处理模数 1:它不对整数施加限制。扩展 Euclid 和 CRT 的中间乘积可能超过原输入,即使最终剩余值能放下亦然。安全类型取决于算法及输入界;溢出后才取模不能撤销溢出。Euclid 迭代次数对输入比特长度是线性的,并不表示任意大整数的每次算术操作都有常数比特成本。
把几何测试写成完整程序
对非退化线段 ,定义 onSegment(A,B,P) 要求定向值为零,且 分别位于 A、B 对应坐标的闭区间内。对一对线段,先测四个严格定向值是否构成真正交叉;若任何定向值为零,对相应端点执行 onSegment,便涵盖共用端点及共线重叠。一条线段退化成点时,对另一线段执行点在线段上的测试;两条均是点时比较两点。这些惯例很重要:从闭线段改为开线段,端点接触是否算相交便会改变。
定向值是有符号三角形面积的两倍,其大小却不是欧氏距离(Euclidean distance)。正负号只判定左、右或共线;计算距离需要不同的归一化。分类多边形时,即使局部转向一致,也需顶点次序及简单多边形等适当假设。自相交顶点序列的有符号面积需要不同解读,不能默默当作一般简单多边形。应区分数学输入契约与实现它的计算检查。
二进制快速幂:保持乘积不变量
对非负整数指数 及整数模数 ,平方乘法把每个乘积模 化简。初始 result=1 mod m、base=a mod m、e=E,其中 e 是尚未处理的指数。若 e 为奇数,先把 result 乘 base;无论奇偶,都把 base 平方并把 e 换为其整数一半。指数零返回模 的乘法单位元; 时其标准代表为 0。负指数需要逆元,不属此简单程序范围。
定理 17.1.8
(平方乘法的不变量)
在每一轮开始时,result * base^e 模 同余于 。特别地,当 e=0 时,result 的值就是 。
证明
(不变量在每一轮中保持成立)
初始时 result * base^e 等于 。设不变量在某一轮开始时成立,写 ,。这一轮把新结果设为 result * base^r,新底数设为 base^2,新指数设为 ,一律模 。于是新结果乘以(新底数)的 次方,同余于 result * base^r * base^(2q) result * base^e,而它同余于 。当 时指数严格减小为 ,所以最终达到 ,此时不变量化为 result 。
例题 17.1.9
(计算 )
例如求 。初始结果 1、底数 3、指数 13;最低位为 1,结果变 3,平方得 9,指数减半为 6。指数 6 的最低位为 0,保留结果 3,9 平方模 17 得 13,指数减半为 3。最低位为 1,结果变 ,13 平方得 16,指数减半为 1。最后一位为 1,结果变 ,指数变 0,故答案是 12。实现可以省略最后一次没有用到的平方,但仍须避免中间乘积溢出。
每轮把剩余指数减半,故重复平方法需要对数数目的算术操作。这个计数不同于任意大整数乘法的比特复杂度,也不同于避免固定宽度溢出的模乘例程成本。若 、 有公因数,正整数幂的计算仍然有效;只有使用逆元的推理需要互素。区分算法不变量与用来缩减指数的定理,能避免在假设不成立时误用 Fermat 定理。
几何程序也须类似地检查叉积符号的边界。在宽类型中先做坐标相减再相乘;若先溢出才转型,已经太迟。在明确分析误差容许度下,双精度近似可能合理;但整数坐标题使用足够宽的精确表示,便可直接测试是否等于零。输入界必须涵盖相减、乘积及最后的差,而不只涵盖每个坐标。
模算例的最后核对应代回原系统,而不只代回缩减式。上述 19 除以 6 余 1、除以 8 余 3;加上最小公倍数 24 后两个余数仍保持。这既核对了所列代表,也解释如何表示整个剩余类。
相容条件变成关于两个理想之和的陈述。
通往推广的路径
从整数到理想
相容条件变成关于两个理想之和的陈述。
在 中, 生成理想 ,所以条件 就是 。在任何交换环中,对理想 ,方程组 、 有解,当且仅当 ,且解构成模 的一个剩余类。在 中, 与 的交是 。
练习
快速检查
(判断 是否有解;若有,列出模 的所有解。)
先计算最大公因数。
解答 · 答案
这里 而 ,所以有解。除以 得 。因为 , 的逆元为 ,所以 。模 的剩余类为 ,恰好 个。验算:、、。
快速检查
(解 与 。)
检查 是否整除 。
解答 · 答案
整除 ,所以方程组相容。写 。第二个条件为 ,即 ,所以 。取 得 ;由于 ,解为 。验算:,。
快速检查
(从 到 的闭线段与从 到 的闭线段是否相交?)
四个点都在同一条直线上。
解答 · 答案
所有点都在 上,所以四个定向值都是零,严格正负号测试不适用。 的包围区间 与 ( 同理)共有值 ,而点 在两条闭线段上。所以它们恰好相交于一点,即公共端点 。
快速检查
(追踪平方乘法计算 。)
从 result 为 1、base 为 2、指数为 10 开始。
解答 · 答案
指数 10 为偶数:result 仍为 1,base 变为 ,指数 5。指数 5 为奇数:result 变为 ,base 变为 ,指数 2。指数 2 为偶数:base 变为 ,指数 1。指数 1 为奇数:result 变为 ,base 变为 ,指数 0。答案为 ,与 一致。