Skip to content

模

取餘數。

性質

  • 加法：
  • 減法：
  • 乘法：
  • 次方：
  • 加法結合律：
  • 乘法結合律：
  • 加法交換律：
  • 乘法交換律：
  • 結合律：

同餘

如果 ，我們會說 在模 下同餘。

以下為性質：

  • 整除性：
  • 遞移性：若
  • 保持基本運算：
  • 放大縮小模數：

快速冪

我們常常遇到求 為多少的題目，最簡單的作法是用迴圈花 次算出答案，但是在 很大時就無法快速算出。這時如果拆成 ，先分別計算在乘起來，這樣只要花費 的時間即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
T pow(int a, int b, int c)
{ // calculate a^b%c
    T res = 1, tmp = a;
    for (; b; b >>= 1)
    {
        if (b & 1)
            res = res * tmp % c;
        tmp = tmp * tmp % c;
    }
    return res;
}

模逆元

模逆元是取模下的反元素，即為找到 使得 。

整數 在 下要有模反元素的充分必要條件為 互質。

模逆元如果存在會有無限個，任意兩相鄰模逆元相差 。

方法一：擴展歐基里德演算法

貝祖定理

令 為非 整數，存在整數解 使得

從上文可得知，如果 ，則 在 下有模反元素，又根據貝祖定理，可知存在整數 ，使得 ，這裡的 即為 的反元素。我們可以修改找最大公因數的辦法，找出 的模逆元，這個算法稱為擴展歐基里德演算法。這個演算法可以推廣到 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
// ax+by=c
int extgcd(int a, int b, int c, int &x, int &y)
{
    int d = a;
    if (b)
    {
        d = extgcd(b, a % b, c, y, x);
        y -= (a / b) * x;
    }
    else
    {
        x = c;
        y = 0;
    }
    return d;
}

方法二：快速冪

根據歐拉定理，如果 ，則 ，將式子稍微改變一下，我們得出 ， 是 在 下的一個模逆元。可以利用快速冪計算 算出模逆元。

中國剩餘定理 (Chinese Remainder Theorem)

中國剩餘定理，又稱中國餘數定理，是數論中的一個關於一元線性同餘方程組的定理。用來解決像下面這種問題：

"有物不知其數，三三數之剩二，五五數之剩三，七七數之剩二。問物幾何？"，這題答案為

列出這種問題的式子（設 兩兩互質）：

解決這類問題最簡單是用枚舉來求解，不過如果範圍太大就會吃 TLE 了。因此我們先列出 個數字 :

分別算出答案後，根據加法在模運算下的性質， 個數字的和，正是我們想要的答案。

將題目分成 個式子後，難度一下降低許多，現在我們只要會解開每個式子就行了。以下以 為例：

顯然整除 ，令 ，可列出式子 。於是原式就變成找模逆元的問題。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
LL P = 1, ans = 0;
for (int i = 0; i < n; ++i)
    P *= m[i];
for (int i = 0; i < n; ++i)
{
    LL a = P / m[i], x, y;
    extgcd(a, m[i], x, y);
    ans = (ans + r[i] * a * x) % P;
}
cout << (ans + P) % P << '\n';

例題練習

  1. Discrete mathematics - Chinese Remainder Theorem ↩