模运算

数学与数论

说明

每步取模避免中间结果无界增长；负数需归一化到非负余数。

分析

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

图解推演

8×7 mod 10 可把 7 拆成 1+2+4，用 8、16 mod 10=6、32 mod 10=2 累加，结果 (8+6+2) mod 10=6。逐次取模限制状态大小，但 a+a 与 result+a 的中间值仍可能溢出；负输入也要先规范到非负余数范围。

查看图表代码

适用前提与边界

mod 必须为正，ModMultiply 还要求乘数 b≥0；它只归一化 a，负 b 不会进入循环。若要处理负乘数，调用前先把 b 规范到 [0,mod)；例如 ModMultiply(8,-7,10) 按现有代码会返回 0，而数学上的非负余数应为 4。对极大 int，中间加法以及归一化表达式中的加法仍须避免溢出。

示例输入与调用

fmt.Println(ModAdd(8, 7, 10), ModMultiply(8, 7, 10))

运行输出

5 6

完整 Go 示例

package main

import "fmt"

func ModAdd(a, b, mod int) int {
	x := ((a%mod+b%mod)%mod + mod) % mod
	return x
}
func ModMultiply(a, b, mod int) int {
	result := 0
	a = ((a % mod) + mod) % mod
	for b > 0 {
		if b&1 == 1 {
			result = (result + a) % mod
		}
		a = (a + a) % mod
		b >>= 1
	}
	return result
}

func main() {
	fmt.Println(ModAdd(8, 7, 10), ModMultiply(8, 7, 10))
}