一、模运算 模运算是大数运算中的常用操作。如果一个数太大，无法直接输出，或者不需要直接输出，可以把它取模后缩小数值在输出。
定义模运算为 a 除以 m 的余数，记为：a mod m = a % m
取模的结果满足 0 <= a mod m <= m-1,题目用给定的 m 限制计算结果的范围。例如 m = 10，就是取计算结果的个位数。
二、同余
1.别称：同余定理可以说是同余关系。
2.定义：两个整数a和b，若它们除以m所得到的余数相等，则称a和b对于模m同余 或 a同余于b模m。
一般记作：a≡b(mod m)
读作：a同余于b模m，或读作 a与b对于模m同余。
定理一：a≡b(mod m) ,当前仅当 m | (a-b)。
定理二：a≡b(mod m) ,当前仅当存在 k 使得 a=b+m*k。
例如，5同余于11模3：11 ≡ 5 (mod 3)
因为11 − 5得出6，它整除于3。或者等价的说，这两个数除以3得到相同的余数：
11 = 3×3 + 2
5 = 1×3 + 2
三、同余的性质
⚪对称性：a≡b(mod m) 则 b≡a(mod m)
⚪传递性：a≡b(mod m) ，b≡c(mod m) 则 a≡c(mod m)
⚪同加性：a≡b(mod m) 则 a+c≡b+c(mod m)
⚪同乘性：a≡b(mod m) 则 a*c≡b*c(mod m) ;
⚪a≡b(mod m),c≡d(mod m) 则 a*c≡b*d(mod m)
⚪同幂性：a≡b(mod m) 则 an≡bn(mod m)
⚪ a%p=x， a%q=x，且 p和q互质，则a%(p*q)=x
然而，对除法取模进行下面的类似操作是错误的：
（a/b) mod m = ((a mod m) / (b mod m)) mod m
例如，(100/50) mod 20 = 2，(100 mod 20) / (50 mod 20) mod 20 = 0，两者不相等。除法的取模需要用到逆元。