C++取模运算实现详解

一、基本概念

在计算机科学中，取模运算是指求出一个数除以另一个数的余数（也叫模数）。例如，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


   
四、示例代码

   
以下是一个使用同余定理实现快速幂的示例代码。该代码可用于计算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;
    }