一、模运算 模运算是大数运算中的常用操作。如果一个数太大，无法直接输出，或者不需要直接输出，可以把它取模后缩小数值在输出。
定义模运算为 a 除以 m 的余数，记为：a mod m = a % m
取模的结果满足 0 <= a mod m <= m-1,题目用给定的 m 限制计算结果的范围。例如 m = 10，就是取计算结果的个位数，参考 HUD 1061 题 ，求 nn ,n <= 109 ,输出结果的个位数。
分配率：取模操作满足以下性质
加：(a+b) mod m = ((a mod m) + (b mod m)) mod m
减：(a-b) mod m = ((a mod m) – (b mod m)) mod m
乘：(a*b) mod m = ((a mod m) * (b mod m)) mod m
然而，对除法取模进行下面的类似操作是错误的：
（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，两者不相等。除法的取模需要用到逆元。
一些恒等式：
(a mod n) mod n = a mod n。
对所有的正数 x 有：nx mod n = 0。
费马小定理(Fermat’s little theorem)是数论中的一个重要定理，在1636年提出，其内容为： 假如a是整数，p是质数，且gcd(a,p)=1，那么 ap-1≡1(mod p)，即：假如a是整数，p是质数，且a,p互质(即两者只有一个公约数1)，那么a的(p-1)次方除以p的余数恒等于1。一般使用的是快速幂实现费马小定理的内容，并且当a是素数时，ap-2是a的逆元。
除法定义： 仅当式子右侧有定义时，即 b、n 互质时有：ab mod n = [(a mod n)(b−1 mod n)] mod n，其他情况为未定义的。
乘法逆元：[(ab mod n)(b−1 mod n)] mod n = a mod n.
更快的实现：对2 的 n 次幂的模，可以通过逐位与运算实现(只适用于正数)。即 x % 2n == x & (2n-1) 也可以写为x % 2n == n&((1<<k)-1)。例如：假定 x 为正数： x%2 == x&1 x%4 == x&3 x%8 == x&7
二、同余
1.别称：同余定理可以说是同余关系。
2.定义：是指对于一个正整数n，如果a−b整除于n（还有一个等价的条件是它们除以n得出同样的余数），则两个整数a和b被称为同余模n。一般记作：a≡b(mod n)，读作a同余于b模m，或读作a与b关于模m同余（其中同余于的符号是同余相等符号≡）
例如，5同余于11模3：11 ≡ 5 (mod 3)
因为11 − 5得出6，它整除于3。或者等价的说，这两个数除以3得到相同的余数：
11 = 3×3 + 2
5 = 1×3 + 2