数论杂项

  1. 1. 取余(区别python的取模)
    1. 1.1. 取模分配律(除法例外)
    2. 1.2. 取模同余定理

数论杂项

取余(区别python的取模)

注意:对于取余,下面统一用%符号,对于取模,统一用mod关键字
区别于python,java中的负(正)数 / 负(正)数 = 答案,这个答案会向0靠近,取模的结果就是剩下的数,例如:

7/4=137/4=137/4=13\begin{aligned} {-7} / 4 &= {-1}余{-3} \\ {-7} / {-4} &= {1} 余 {-3} \\ 7 / {-4} &= {-1} 余 3 \end{aligned}

取模分配律(除法例外)

除法的取模需要进行逆元运算才能求解。

(a+b) mod p=(a mod p+b mod p) mod p(ab) mod p=(a mod pb mod p) mod p(ab) mod p=(a mod pb mod p) mod pab mod p=((a mod p)b) mod p\begin{aligned} (a + b)\ mod \ p &= (a\ mod \ p + b\ mod \ p)\ mod \ p \\ (a - b)\ mod \ p &= (a\ mod \ p - b\ mod \ p)\ mod \ p \\ (a * b)\ mod \ p &= (a\ mod \ p * b\ mod \ p)\ mod \ p \\ a ^ b\ mod \ p &= ((a\ mod \ p) ^ b)\ mod \ p \end{aligned}

取模同余定理

对于(ab) mod k=0(a - b) \ mod \ k = 0,则有a mod k=b mod ka \ mod \ k = b \ mod \ k。对于python,本身就是取模,直接取模运算即可。
对于java的取余需要特殊处理一下,(a % k+k) % k=(b % k+k) % k(a \ \% \ k + k)\ \% \ k = (b \ \% \ k + k)\ \% \ k

用途:
974. 和可被 K 整除的子数组 - 力扣(LeetCode),前缀和处理后,(sum[j] - sum[i]) % k = 0的换处理。

字符串Hash文章中 字符串Hash,代码里面取余(大于k,取余变小)后,再去减(小于k,不变)可能出现负数情况的处理(见代码注释)。转换为整数。