首先来看一下在模意义下的基本运算法则有哪些:
(a + b) % p = (a%p + b%p) %p
(a - b) % p = (a%p - b%p + p) %p
(a * b) % p = (a%p * b%p) %p
(a / b) % p = (a%p / b%p) %p
(错)
前三个式子都是正确的,第四个不正确,我们随便举个例子就明白了。
(99/4)%5=(24)%5=4;
(99/4)%5=((99%5)/(4&5))%5=(4/4)%5=1;
显然第四个式子不正确。
但是对于一些题目,我们必须在中间过程中进行求余,否则数字太大,电脑存不下,那如果这个算式中出现除法,我们是不是对这个算式就无法计算了呢?
答案当然是NO,Very very no!
这时就需要逆元了
乘法逆元可根据欧拉定理或费马小定理简便推出。
支持作者完善!
好的好的感谢提醒!!!
第二个式子:(a - b) % p = (a%p - b%p) % p。严谨的来说是(a - b) % p = (a%p - b%p + p) % p。因为两数相减可能出现负数。所以要先加p,保证 % p的不是负数(c++模负数可能会出问题)
正确的