取模问题

发表于 | 更新于 | 分类于 ，

1. 取模的数学规则

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;
//灵活运用性质1和性质5
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);

证明略。