2025/11/12

[质数分解] - [最小公倍数] - [最大公约数] 任何一个数都可以表示为质数幂的乘积

eg.

$12 = 2^2 \times 3^1$

$8 = 2^3 \times 3^0$

GCD 被转换为对幂求最小值：

$gcd(12,8) = 2^{min(2,3)} \times 3^{min(1,0)} = 2^2 \times 3^0 = 4 $

LCM 被转换为对幂求最大值：

$lcm(12,8) = 2^{max(2,3)} \times 3^{max(1,0)} = 2^3 \times 3^1 = 24 $

2025/01/21

[质数] - [奇数]

除了2以外的所有质数都是奇数 奇数p有性质 p | (p-1) = p 并且 x | (x+1) = p 中最小的x就是把p二进制末尾连续1的最后一个替换为0