风灵无畏OI
此站用来记录个人的OI成长史，以后会将个人做的每道题的解题报告发到此站上来，希望大家喜欢！（如有讲得不好的地方请大家指出，我会加以改进。当然也有可能传上来一点乱七八糟的东西）
注：转载文章请标上原址，毕竟码字很辛苦！谢谢！
模运算
以下内容一部分来自百度百科，也有一部分来自度娘。。。。。。（纯为自己做的笔记，方便以后自己好回忆）
【模运算的原理】https://baike.baidu.com/item/模运算
Turbo Pascal对mod的解释是这样的： A Mod B=A-(AdivB) * B （div含义为整除）
【基本概念】
其中 k 、 r是整数，且 0< r<p，称 k 为 n 除以 p的商， r为 n除以 p 的余数。
p对于正整数和整数 a , b，定义如下运算：
取模运算：a % p（或a mod p），表示a除以p的余数。
模p加法：(a + b) % p ，其结果是a+b算术和除以p的余数，
也就是说，(a+b) = kp +r，则(a + b) % p = r。
模p减法：(a-b) % p ，其结果是a-b算术差除以p的余数。
模p乘法：(a * b) % p，其结果是 a * b算术乘法除以p的余数。
【说明】
1.同余式：正整数a，b对p取模，它们的余数相同，记做 a ≡ b % p或者a ≡ b (mod p)。
2. n % p得到结果的正负由被除数n决定,与p无关。
例如：7%4 = 3， -7%4 = -3， 7%-4 = 3， -7%-4 = -3
（具体计算可以有上面给出的模运算原理来推出： A Mod B=A-(AdivB) * B）
【基本性质】
（1）若p|(a-b)，则a≡b (% p)。例如 11 ≡ 4 (% 7)， 18 ≡ 4(% 7)
对（1）的解释：
若p能整除a-b.则a恒等于b加上p的整数倍.
即总是存在正整数n,使得a=b+np.换个说法也就是:a除以p的余数恒等于 b
（2）(a % p)=(b % p)意味a≡b (% p)
（3）对称性：a≡b (% p)等价于b≡a (% p)
（4）传递性：若a≡b (% p)且b≡c (% p) ，则a≡c (% p)
【运算规则】
模运算与基本四则运算有些相似，但是除法例外。其规则如下：
（1） (a + b) % p = (a % p + b % p) % p
（2） (a - b) % p = (a % p - b % p) % p
（3） (a * b) % p = (a % p * b % p) % p
（4） (a^b) % p = ((a % p)^b) % p
结合律：
（5） ((a+b) % p + c) % p = (a + (b+c) % p) % p
（6） ((a*b) % p * c)% p = (a * b*c) % p // (a%p*b)%p=(a*b)%p
交换律：
（7） (a + b) % p = (b+a) % p
（8） (a * b) % p = (b * a) % p
分配律：
（9） ((a +b)% p * c) % p = ((a * c) % p + (b * c) % p) % p
【重要定理】
（10） 若a≡b (% p)，则对于任意的c，都有(a + c) ≡ (b + c) (%p)；
对（10）的解释：
因为由这个a≡b (% p)可以推出这个(a % p)=(b % p)
而由(a + c) ≡ (b + c) (%p)可以推出（（a +c ）% p））=（（b +c） % p））
可以拆成(a + c) % p = (a % p + c% p) % p
（（b +c） % p） = (b % p+ c % p) % p
可知(a % p + c% p) % p = (b % p+ c % p) % p
将两边相同的减去得到(a % p)=(b % p)。
（11） 若a≡b (% p)，则对于任意的c，都有(a * c) ≡ (b * c) (%p)；
对（11）的解释：此式子可以按照由上面对（10）的解释推出
（12） 若a≡b (% p)，c≡d (% p) 则
(a + c) ≡ (b + d) (%p)
(a - c) ≡ (b - d) (%p)
(a * c) ≡ (b * d) (%p)
(a / c) ≡ (b / d) (%p)
以1来解释：
我们可以把a≡b (% p)拆成(a % p)=(b % p) *
同样c≡d (% p) 拆成(c % p)=(d % p) **
再把(a + c) ≡ (b + d) (%p)拆成(a + c % p)=(b + d % p)
推出(a % p + c % p) % p =(b % p + d % p) % p ***
再由*和* *可知* * *是正确的
【两条推论】
如果 a ≡ b ( % n * c )，并且c | a，（这个表示a能被c整除）那么，
a / c ≡ b / c ( % n)
如果 a ≡ b ( % n * m )，那么，a ≡ b ( % m )
下面来解释一下这两条推论：
推论1：
我们可以把这个a ≡ b ( % n * c )换成这个a % ( n * c ) = b,再可以换成这个
a = k * n * c + b,(k 为一个正整数)，然后左右两边可以同除以一个C，于是就变成了
a / c = k * n + b / c,(其中b/c为整数，不是因为“/”表示整除)是因为：c|a，我们可以表示
成a=y*c，那我们可以把这个式子换成y * c - k * n * c = b,把式子处理一下，变成
( y - k * n ) * c = b,所以c是b的一个因子，所以b/c为整数。
推论2：
a ≡ b ( % n * m )这个式子可以表示成a % n * m = b,变形成a - k * n * m = b,
因为a ≡ b ( % m )这个式子表示成这样a % m = b % m,而a - k * n * m = b，所以可以写成a % m = ( a - k * n * m ) % m,就等于a % m = a % m，所以这个推论成立。
（大概就是这样的吧，如果有错，请各位大佬指出！）