1 基本性质
((a+b)% p = (a%p + b%p)%p)
((a-b)% p = (a%p – b%p)%p)
((a*b)% p = (a%p * b%p)%p)
((a^b)% p = ((a%p)^ b)%p)
除法不满足,但是根据费马小定理,当p是质数,且a和p互质的时候,可以将除法写成:((a/b) % p = (a * a^{p-2}) % p);其中(a^{p-2})叫做b的逆元
2 特殊用法
算法竞赛看到很多选手取模的时候都在加法的括号里加上一个mod再模mod;比如 (ans = (A+mod)%mod) 或者 (ans = (A+k*mod)%mod) ;因为括号里面的mod或k*mod模mod都是0,所以有人认为这里可能是多余的。
其实这么做是为了防止负数,出现负数的话就会导致不同语言取模运算结果不同,常用法是在减法的时候用,即:((a-b+mod)%mod)
关于负数的取模运算,涉及到整除运算和取余数的运算,整除运算方法就不统一
整除运算主要有向上取整、向下取整、向0取整三种
计算机计算负数的模,不同语言得的结果不一样,C/Java 用 截断舍尾,Python 用 地板
参考博客:
最新评论