1.1 基本四则运算

[
begin{cases}
(a + b) bmod p = (a bmod p + b bmod p) bmod p\
(a - b) bmod p = (a bmod p - b bmod p + p) bmod p\
(a * b) bmod p = (a bmod p * b bmod p) bmod p\
(a ^ b) bmod p = ((a bmod p) ^ b) bmod p\
(a bmod p) bmod p = a bmod p
end{cases}
]

1.2 其他性质

• 交换律

[
(a + b) bmod c = (b + a) bmod c\
(a * b) bmod c = (b * a) bmod c
]

• 结合律

[
((a+b) bmod p + c) bmod p = (a + (b+c) bmod p) bmod p\
((a * b) bmod p * c) bmod p = (a * (b * c) bmod p) bmod p\
]

• 分配律

[
((a +b)bmod p * c) bmod p = ((a * c) bmod p + (b * c) bmod p) bmod p
]

2. 重要应用

有一种常见的题型，要求对一个大整数求模运算， 这时我们就可以灵活运用求模运算的性质。

例如下面这题:

求斐波那契数列 (F_n) 除以10007的余数是多少(1 <= n <= 1000000)

这里很显然主要的问题就是溢出问题，一下这种写法很显然会溢出:

1
2
3
4
5
6
7
8

long a = 1, b = 1, res = 2;
for (int i = 3; i <= n; ++i)
{
    res = a + b;
    a = b;
    b = res;
}
System.out.println(res % 10007);

利用取模的性质，我们可以改写为:

1
2
3
4
5
6
7

for (int i = 3; i <= n; ++i)
{
    res = (a + b) % 10007;
    a = b;
    b = res;
}
System.out.println(res);

再举一个例子:

输入n，求前n个阶乘相加后的数的后6位(不包含前导0)。n <= 10^6

如果我们不利用性质，就会写出一个比较危险的代码:

1
2
3
4
5
6
7
8
9

long factorial = 1;
long sum = 0;
long mod = 1000000;
for(int i = 1; i <= n; ++i)
{
    factorial *= i;
    sum += factorial;
}
System.out.println(sum % mod);

显然百分百会溢出。但是如果我们更改一下，重复利用数学性质，则有:

1
2
3
4
5
6
7
8
9
10

long factorialx = 1;
long sumx = 0;
long mod = 1000000;

for(int i = 1; i <= n; ++i)
{
    factorialx = (factorialx * i) % mod;//等价与factorialx + i % mod, 但这么做factorialx有溢出的风险
    sumx = (sumx + factorialx) % mod;//等价于sumx + factorialx % mod，但这么做sumx有溢出的风险
}
System.out.println(sumx % mod);

证明略。