数学、位运算与几何

本页按场景选择方法；通过各条目链接阅读完整推演、源码和输出。

每个 package main 独立保存为 main.go，不要合并重名 Point；使用 Go 1.22+。本轮未执行，输出是静态推导。计数与几何乘加要求所有中间值均可用 int 表示，尤其相交测试会相乘两个叉积；筛法要求 n 非负、分解要求 n >= 1、幂指数非负。

要解决的问题	可选方法	选择前确认
约分、分解一个整数或枚举范围内素数	最大公约数、质因数分解、埃氏筛	试除适合单个数，筛法以 O(n) 空间预处理整个范围。
计算组合数或加速幂与线性递推	组合数、快速幂、矩阵快速幂	组合数一维倒序更新；快速幂指数非负，矩阵示例为 2×2，均需关注溢出。
让算术结果保持在模范围	模运算	mod 必须为正，负余数需归一化；逐步取模仍不能忽略中间加法溢出。
紧凑保存布尔状态、比较置位差异或枚举子集	位掩码、汉明距离、子集位枚举	位宽有限；子集位枚举只输出非空子集，结果仍指数增长。
判断方向、线段接触或点集边界	点积与叉积、线段相交、凸包	示例相交包含端点与共线重叠；凸包省略共线中间点且会重排输入。
统计同时活跃的区间数量	扫描线	示例采用半开区间，同坐标先处理终点；端点定义决定事件顺序。
从未知长度的数据流等概率取一个样本	蓄水池抽样	第 i 项以 1/i 概率替换；固定随机种子用于复现，可另传随机源。

求公约数、质因子、素数与组合数

欧几里得算法

正文、推演与完整示例：欧几里得算法。

gcd(a,b)=gcd(b,a mod b)，因为能同时整除 a 和 b 的数也能整除余数。每轮让第二个数变小，直到余数为零。 结束时的非零值即最大公约数。

它还能配合最小公倍数计算和分数约分；涉及负数时示例把最终结果转成非负，但最小 int 的绝对值可能无法用 int 表示，本例不接受该极值。GCD(0,0) 按实现返回 0。

质因数分解

正文、推演与完整示例：质因数分解。

示例返回带重复次数的因子列表；非常大的整数通常需要更先进的分解算法。

埃氏筛

正文、推演与完整示例：埃氏筛。

预处理时间约 O(n log log n)、空间 O(n)，适合一次求出范围内许多素数。

组合数

正文、推演与完整示例：组合数。

组合数满足帕斯卡恒等式：选择某元素或不选它，得到相邻两项之和。用一维数组倒序更新，避免本轮新值覆盖还需要读取的上一轮状态。 空间 O(k)。

结果增长很快，n 较大时 Go int 会溢出。

用模运算与快速幂控制计算过程

模运算

正文、推演与完整示例：模运算。

模运算把整数结果限制在 0 到 mod−1 的范围内，常用于计数、哈希和数论。加法与乘法可以逐步取模；示例乘法按位累加，避免直接计算 a×b。 负数取模后还需归一化到非负余数。

mod 必须为正，ModMultiply 的 b 必须非负；负 b 会跳过循环而不能得到正确乘积。对极大 int 的中间加法仍要注意溢出，本例要求归一化和相加的中间值均可由 int 表示。

快速幂

正文、推演与完整示例：快速幂。

把指数写成二进制：某一位为 1 时，把当前底数乘入答案；每轮底数平方、指数右移。这样只需对数次乘法。 时间 O(log exponent)。

示例处理非负整数指数且使用普通 int，负指数或溢出风险需要另行处理。

矩阵快速幂

正文、推演与完整示例：矩阵快速幂。

示例处理 2×2 矩阵；大数计算需要考虑溢出或取模。

表示位集合、比较差异与枚举子集

位掩码

正文、推演与完整示例：位掩码。

第 i 位可以表示第 i 个功能是否启用、元素是否已选等布尔状态。按位或设置该位，按位清除移除它，按位与检查它。 单个机器字中的添加、移除和判断均为 O(1)。

一个机器字只能容纳有限个状态；超过字长时要使用多个字或位集合。

判断 2 的幂

正文、推演与完整示例：判断 2 的幂。

必须先排除零，否则无符号整数的减法会下溢，且零本身也不是 2 的幂。

汉明距离

正文、推演与完整示例：汉明距离。

比较很长的二进制串时，可以分块处理并累加每块的置位数。

位运算枚举子集

正文、推演与完整示例：位运算枚举子集。

给定 mask，(sub−1)&mask 会得到下一个更小且只包含原掩码置位的子集。循环直到 sub 为零，能枚举全部非空子集。 包含 k 个置位时枚举耗时 O(2^k)。

包含 k 个置位时共有 2ᵏ−1 个结果，指数增长仍然不可避免。

判断几何关系与统计区间重叠

点积与叉积

正文、推演与完整示例：点积与叉积。

点积 a·b 与向量夹角和投影有关，常用于判断朝向与计算长度。二维叉积 a×b 的符号区分从 a 转向 b 是左转、右转还是共线。 二维向量上的这些运算均为常数时间。

坐标值很大时，乘法可能超出 int 范围，需要更宽的数值类型。

线段相交

正文、推演与完整示例：线段相交。

示例把端点接触和共线重叠都视为相交。

凸包

正文、推演与完整示例：凸包。

单调链先按 x、y 排序，再依次构建下凸壳和上凸壳。遇到非左转时删除中间点，保证边界始终凸。 时间 O(n log n)。

示例会修改输入切片的顺序，并省略同一直线上的中间边界点；是否保留这些点取决于应用。

扫描线基础

正文、推演与完整示例：扫描线基础。

最大活跃数就是最大并发覆盖数量。

从未知长度的数据流抽取一个样本

蓄水池抽样

正文、推演与完整示例：蓄水池抽样。

处理第 i 个元素时，以 1/i 的概率替换当前样本。归纳可知，处理完 i 个元素后每个元素仍以 1/i 的概率被保留，因此无需事先知道流长度。 无需保存整条数据流。

示例固定随机种子便于复现；实际场景可传入自己的随机源。

静态自检

ModMultiply(8,-7,10) 是否满足本例前提？再判断半开区间 [1,2) 与 [2,3) 是否重叠。提示：看循环条件和同坐标事件顺序。

参考解法

不满足，b 必须非负，负数会直接跳过循环；两个半开区间不重叠，同坐标先处理终点再处理起点。需要支持有符号乘法应另设计归一化契约。