数论杂项
取余(区别python的取模)
注意:对于取余,下面统一用%符号,对于取模,统一用mod关键字
区别于python,java中的负(正)数 / 负(正)数 = 答案,这个答案会向0靠近,取模的结果就是剩下的数,例如:
−7/4−7/−47/−4=−1余−3=1余−3=−1余3
取模分配律(除法例外)
除法的取模需要进行逆元运算才能求解。
(a+b) mod p(a−b) mod p(a∗b) mod pab mod p=(a mod p+b mod p) mod p=(a mod p−b mod p) mod p=(a mod p∗b mod p) mod p=((a mod p)b) mod p
取模同余定理
对于(a−b) mod k=0,则有a mod k=b mod k。对于python,本身就是取模,直接取模运算即可。
对于java的取余需要特殊处理一下,(a % k+k) % k=(b % k+k) % k
用途:
974. 和可被 K 整除的子数组 - 力扣(LeetCode),前缀和处理后,(sum[j] - sum[i]) % k = 0的换处理。
字符串Hash文章中 字符串Hash,代码里面取余(大于k,取余变小)后,再去减(小于k,不变)可能出现负数情况的处理(见代码注释)。转换为整数。