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<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;
    }