【NC23046】华华教月月做数学

题目

华华教月月做数学

考虑数据溢出的问题

思路

题目要求很简单，就是算 a a a 的 b b b 次方的结果对 p p p 取模的值。

当这些数都很小的时候，当然可以直接先求幂再取模，但现在的问题是数据很大，以至于两个数相乘都会溢出。所以不能使用普通的 a × b   m o d   p a\times b\ mod\ p a×b mod p 这种形式来对两个数的积取模。

意思就是说还要想办法让两个数相乘不要溢出。

我们知道一个正整数可以写成二进制形式，比如 5 5 5 可以写成 10 1 2 101_2 1012​，那么 3 × 5 3\times 5 3×5是不是就相当于 3 × 10 1 2 3 \times 101_2 3×1012​ 呢？再由二进制的意义可以知道 5 = 10 1 2 = 1 × 2 0 + 0 × 2 1 + 1 × 2 2 5 = 101_2=1\times 2^0+0\times 2^1+1\times 2^2 5=1012​=1×20+0×21+1×22，那么 3 × 5 = 3 × ( 1 × 2 0 + 0 × 2 1 + 1 × 2 2 ) = 3 × 1 × 2 0 + 3 × 0 × 2 1 + 3 × 1 × 2 2 3\times 5=3\times (1\times 2^0+0\times 2^1+1\times 2^2) = 3 \times 1\times 2^0+3\times 0\times 2^1+3\times1\times 2^2 3×5=3×(1×20+0×21+1×22)=3×1×20+3×0×21+3×1×22，为什么要特意地将乘法转化为加法呢？

很明显，加法比乘法更不容易溢出并且容易取模。

上述的形式 3 × 1 × 2 0 + 3 × 0 × 2 1 + 3 × 1 × 2 2 3 \times 1\times 2^0+3\times 0\times 2^1+3\times1\times 2^2 3×1×20+3×0×21+3×1×22 还不够直观，因为即使是写成这个样子也不知道如何写代码。
如果设置一个临时值来存储每一项，一个答案来累加每一项，那么上述形式可以写成：

问号处填什么比较好？很显然，应该填 3 × 2 3\times 2 3×2

到这一步，应该就有一点思路了：

1. 从低位到高位枚举某个加数的每一位，如果是1，则答案累加临时值并取模，如果是0，则不累加
2. 无论是0还是1，都要将临时值翻倍并取模
3. 由于完全可以由另一个加数来充当临时值，所以不需要定义临时值，直接使用另一个加数即可

到这一步，就算解决了让两个很大的数相乘不至于溢出。那么怎么解决题目的问题呢？

可以很容易地知道， a b   m o d   p a^b\ mod\ p ab mod p 可以类比于 a × b   m o d   p a\times b\ mod\ p a×b mod p，将关键之处的代码修改一下即可。

有趣的一点是，这种算法用于幂的运算时被称为“快速幂”，但是用于乘法时却显得多此一举（为什么不直接乘呢？），相当于是降低了运算效率来解决计算溢出的现实问题。

代码

#include <iostream>
using namespace std;
using ULL = unsigned long long;

// 大整数乘法
ULL big_mult(ULL a, ULL b, ULL p) {
    ULL res = 0ULL;
    while (b) {
        if (b & 1) {
            res = (res + a) % p;
        }
        b >>= 1;
        a = (a + a) % p;
    }
    return res;
}

// 快速幂
ULL quick_pow(ULL a, ULL b, ULL p) {
    ULL res = 1ULL;
    while (b) {
        if (b & 1) {
            res = big_mult(res, a, p);
        }
        b >>= 1;
        a = big_mult(a, a, p);
    }
    return res;
}

int main(void) {
    int t = 0;
    cin >> t;
    ULL a = 0, b = 0, p = 0;
    while (t--) {
        cin >> a >> b >> p;
        cout << quick_pow(a, b, p) << endl;
    }
    return 0;
}