一、基本概念
在计算机科学中，取模运算是指求出一个数除以另一个数的余数（也叫模数）。例如，13除以4的余数为1，记作13 mod 4=1。C++中可以使用%运算符实现取模运算。
二、取模运算的性质
1. 同余定理：
如果a和b是整数，m是一个正整数，且a和b被m整除的余数相同，即a mod m = b mod m，那么我们称a和b对模m同余，记作a ≡ b (mod m)。
同余关系具有如下性质：
（1）自反性：a ≡ a (mod m)
（2）对称性：若a ≡ b (mod m)，则b ≡ a (mod m)
（3）传递性：若a ≡ b (mod m)，b ≡ c (mod m)，则a ≡ c (mod m)
（4）加减乘同余：若a ≡ b (mod m)，c ≡ d (mod m)，则a+c ≡ b+d (mod m)，a-c ≡ b-d (mod m)，ac ≡ bd (mod m)
2. 取模运算规律：
（1）(a+b)%m = (a%m + b%m)%m
（2）(a-b)%m = (a%m - b%m)%m
（3）(a*b)%m = (a%m * b%m)%m
（4）(a/b)%m != (a%m / b%m)%m，但有(a/b)%m = ((a/m)/(b/m))%m
三、常见问题
1. 如何处理负数？
当进行负数取模的运算时，C++标准并没有明确规定取哪个整数作为结果。例如-13 mod 4，在不同的编译器中可能得到不同的结果。如果要求得与数学定义一致的答案，则需使用如下代码：
int mod(int a, int b) {
return (a%b + b) % b;
}
2. 如何处理大数？
如果需要对大数进行取模运算，可以使用字符串或数组表示大数，并使用常规的取模方法逐位计算。以下是一个对大整数取模的模板函数，其中base为进制（例如10）。
string mod(string s, int base, int modNum) {
int remainder = 0;
for (int i=0; i<s.size(); i++) {
remainder = (remainder*base + (s[i]-'0'))%modNum;
}
return to_string(remainder);
}
四、示例代码
以下是一个使用同余定理实现快速幂的示例代码。该代码可用于计算a^b mod c的值。
int quickPow(int a, int b, int modNum) {
int res = 1;
while (b) {
if (b&1) res = res*a%modNum;
a = a*a%modNum;
b >>= 1;
}
return res;
}
原创文章，作者：小蓝，如若转载，请注明出处：https://www.506064.com/n/269984.html
微信扫一扫 
支付宝扫一扫 