算法竞赛系列 | 模运算

模是Mod的音译，读作mó，意为求余。运算是大数运算中的常用操作。如果一个数太大，无法直接输出，或者不需要直接输出，可以把它取模后缩小数值再输出。因为模运算有缩小数值范围的功能，所以常用于哈希计算。

定义取模运算为求a除以m的余数，记为a mod m=a % m。

正整数取模的结果满足 0≤a mod m≤m-1，其含义是用给定的m限制计算结果的范围。例如，m=10，就是取计算结果的个位数。又如，m=2,若余数为0，表示a为偶数，否则a为奇数。

一般的求余都是正整数的操作，如果是对负数求余，不同的编程语言结果可能不同，下面给出3种语言的例子。

C语言和Java：5 % 3，输出2；(-5) %(-3)，输出-2；5 %(-3)，输出2；(-5) % 3，输出-2。计算规则是先按正整数求余，然后加上符号，符号与被除数保持一致。

Python语言的负数求余有点奇怪，如：123 % 10，输出3；123 %(-10)，输出7。原因是Python语言的求余是向下对齐的。

取模操作满足以下性质。

加：(a+b)mod m=((a mod m)+(b mod m))mod m。如果没有限制a、b的正负，C代码中左右可能符号相反、大小相差m; 但是Python代码不存在这个问题。

减：(a-b) mod m=((a mod m)-(b mod m)) mod m。C代码中左右可能符号相反、大小相差m; 但是Python代码不存在这个问题。

乘：(a×b) mod m=((a mod m)×(b mod m)) mod m。

然而，对除法取模进行类似操作：(a/b) mod m = ((a mod m)/(b mod m)) mod m,是错误的。

例如，(100/50) mod 20=2，(100 mod 20)/(50 mod 20) mod 20=0，两者不相等。

需要特别注意。两个大数a和b做乘法取模时，直接用(a×b) mod m=((a mod m)×(b mod m)) mod m可能出错，因为其中的a×b可能溢出，(a mod m)×(b mod m)也可能溢出。用以下代码能在一定程度上得到正确结果。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mul(ll a,ll b,ll m){     //乘法取模：a*b mod m
    a = a%m;                //先取模，非常重要，能在一定程度上防止第10行a+a溢出
    b = b%m;
    ll res = 0;
    while(b>0){             //递归思想
        if(b&1) res=(res+a)% m;  //用b&1判断b的奇偶
        a=(a+a)% m;              //需要保证a+a=2a不能溢出，否则答案错误
        b>>=1;
    }
    return res;
}
int main(){
    ll a = 0x7877665544332211;
    ll b = 0x7988776655443322;
    ll m =  0x998776655443322;    //把m改成比a大的0x7977665544332211，mul()也会出错
    cout << (a%m)*(b%m)%m <<endl; //输出 145407782617487436，错误
    cout << mul(a,b,m);           //输出 411509877096934416，正确
}

(1) b是偶数。此时a×b就等于(a×2)×(b÷2)。

(2) b是奇数。此时a×b等于(a×2)×(b÷2+1) =(a×2)×(b÷2)+(a×2)，多了一个a×2。

代码第9行用b&1判断b的奇偶，如果是奇数，加上多的a×2。第10行求a×2，并取模。第11行求b÷2。

注意用这个代码时，仍要注意a和m的取值。例如，把第18行的m改成比a大的数，mul()也会出错。请仔细分析原因。

提示/