C++64位整型相乘取模的溢出处理（一）

在ACM中做题时经常会出现输出的结果要模以一个数，如模 109 + 7 ，一般来说用64位整型long long（有些编译器是__int64）来保存答案是没有什么问题的，因为 109 + 7 没有超过231- 1 ，即32位整型int也能存得下，int * int 也不会溢出 long long，但是就是有些坑爹的题目取模的数超过int，就有可能出现两个long long类型相乘时溢出的情况，虽然两个long long相乘取模后的结果不超过long long，不过相乘时溢出可能会影响符号位，导致结果为负，再取模，结果也是负的，当然不一定溢出就会变负数。直接上代码

#include <iostream>
using namespace std;

const long long MOD = ;

long long  mul(long long a, long long b) {
    long long ans = , step = a % MOD;
    while (b) {
        if (b & ) ans += step;
        if (ans >= MOD) ans %= MOD;
        step <<= ;
        if (step >= MOD) step %= MOD;
        b >>= ;
    }
    return ans % MOD;
}

int main() {
    cout << mul(, ) << endl;
    return ;
}
           

输出结果对 1018 取模，结果和计算器算的一致。

函数mul的复杂度是 log(n) ，这里的运算次数是 b 的二进制数的长度，当然可以加个判断来降一丢丢运算次数。

原理类似快速幂，把b写成二进制， b 的二进制中的每一个1就表示 2i 个 a ，i表示这个 1 是第几位的（从0开始），把这些个 2i∗a 加起来就是结果了，计算时对中间结果取模。