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 加起來就是結果了，計算時對中間結果取模。