西北工业大学NOJ平台：大数处理专题（共2篇题解）

发表于

前言

大数处理是程序设计中经常会遇到的问题，本篇文章将会介绍两种常见的大数处理方法（主要和取模有关）：

  • 循环取余法
  • 快速幂算法

前置知识

余数

余数指整数除法中被除数未被除尽部分，记作a % b。例如7无法整除3，得到商为2还剩下1，所以7对3取余得到1。

另外有一个概念被称作取模，当a与b同号，两个概念等价，否则的话它们之间有一定差别，这一部分概念不在本题讨论范围内。

越界

在C++11标准中，int类型的储存范围为-2^31到2^31 - 1，long long类型的储存范围为-2^63到2^63 - 1，也就意味着具有相应类型的变量储存的值不应当超出该范围。

(11-20)乘数模

题面信息

题面（乘数模）

解决方法：循环取余法

先推导：当(a + b) % m == c时，((a % m) + (b % m)) % m == c仍然成立：将a表达为a = im + j，其中i = a // m, j = a % m，b表达为b = km + l，系数同理与a。则a * b = (k + i)m + j + l，可知(a + b) % m == (j + l) % m == ((a % m) + (b % m)) % m即证

其中//代表整除，下同。

基于此，将a * b看作b个a相加，套用相关结论即可得到结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <stdio.h>

int main() {
    unsigned long long a, b, m;
    scanf("%llu %llu %llu", &a, &b, &m);
    unsigned long long baseValue = a % m;
    unsigned long long result = 0;
    for (int i = 0; i < b % m; i++) {
        result += baseValue;
        result %= m;
    }
    printf("%llu", result);
}

同样的，这个结论可以推广到乘法：当(a * b) % m == c时，((a % m) * (b % m)) % m == c仍然成立：将a表达为a = im + j，其中i = a // m, j = a % m，b表达为b = km + l，系数同理与a。则a * b = kim^2 + kjm + ilm + jl，可知(a * b) % m == jl % m == ((a % m) * (b % m)) % m即证。

推荐做这道额外练习，巩固所学知识（LeetBook，砍竹子II）：https://leetcode.cn/leetbook/read/illustration-of-algorithm/lhmp26/

(11-20)幂数模

题面信息

题面（幂数模）

解决方法：快速幂算法

要计算a ^ b的具体值，我们可以通过循环执行b次ans *= a来达到要求，不过当b很大时，该算法耗时也很高，为了优化该过程，我们提出快速幂算法，其基本思想如下：

对于一个底数a，幂数b来说，a ^ b的结果等价于：

  • b为偶数，(a * a) ^ (b / 2)；
  • b为奇数，(a * a) ^ (b // 2) * a。

容易证明上述算法正确，该算法仅需进行约log(2, b)次乘法运算，是对上方循环算法的极大优化，被广泛使用于各个场合。

基于此，给出计算a ^ b的快速幂算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
int main(){
    unsigned long long base, power;
    scanf("%llu %llu", &base, &power);
    unsigned long long result = 1;
    while (power) {
        if (power & 1) {
            result = result * base;
        }
        base = base * base;
        power >>= 1;
    }
    printf("%llu\n", result);
}

b & 1为与运算，它在b为奇数时为真。b >>= 1为右移运算，相当于b /= 2

又根据上方结论：(a * b) % m == c时，((a % m) * (b % m)) % m == c仍然成立，在幂运算时同时取余即可达成本题需求。

1
2
3
4
5
6
7
8
9
10
11
12
13
int main(){
    unsigned long long base, power, moder;
    scanf("%llu %llu %llu", &base, &power, &moder);
    unsigned long long result = 1;
    while (power) {
        if (power & 1) {
            result = (result * base) % moder;
        }
        base = (base * base) % moder;
        power >>= 1;
    }
    printf("%llu\n", result);
}

推荐阅读（LeetBook，大数取余思路）：https://leetcode.cn/leetbook/read/illustration-of-algorithm/lx2q6v/。

感谢您的阅读！