Phép chia lấy dư và Số học đồng dư (Modulo 10^9 + 7): giải thích dễ hiểu, code C++ và Python

#include <iostream>
using namespace std;

const long long MOD = 1'000'000'007LL;

// Chuẩn hóa số nguyên x bất kỳ (kể cả số âm) về đoạn [0, m - 1]
long long mod_norm(long long x, long long m = MOD) {
    return ((x % m) + m) % m;
}

// Cộng đồng dư: (a + b) mod m
long long mod_add(long long a, long long b, long long m = MOD) {
    return (mod_norm(a, m) + mod_norm(b, m)) % m;
}

// Trừ đồng dư an toàn không bao giờ bị âm: (a - b + m) mod m
long long mod_sub(long long a, long long b, long long m = MOD) {
    return (mod_norm(a, m) - mod_norm(b, m) + m) % m;
}

// Nhân đồng dư ép kiểu 64-bit tránh tràn số: (a * b) mod m
long long mod_mul(long long a, long long b, long long m = MOD) {
    return (mod_norm(a, m) * mod_norm(b, m)) % m;
}

int main() {
    // Test 1: Chuẩn hóa số âm -7 khi chia lấy dư cho 3 (kết quả chuẩn = 2)
    cout << "Norm(-7, 3): " << mod_norm(-7, 3) << "\n";

    // Test 2: Cộng, trừ, nhân hai số lớn sát ngưỡng 10^9 + 7
    long long a = 1'000'000'005LL; // Đồng dư với -2 (mod 10^9 + 7)
    long long b = 1'000'000'006LL; // Đồng dư với -1 (mod 10^9 + 7)
    cout << "Add: " << mod_add(a, b)
         << " | Sub: " << mod_sub(a, b)
         << " | Mul: " << mod_mul(a, b) << "\n";

    // Test 3: Tính biểu thức (10^9 * 10^9 - 100) mod (10^9 + 7)
    // 10^9 * 10^9 đồng dư (-7) * (-7) = 49; trừ đi 100 rồi cộng MOD ra 999999956
    long long tich = mod_mul(1'000'000'000LL, 1'000'000'000LL);
    cout << "Expr: " << mod_sub(tich, 100) << "\n";

    return 0;
}

MOD = 1_000_000_007


def mod_norm(x: int, m: int = MOD) -> int:
    """Chuẩn hóa số nguyên x bất kỳ về đoạn [0, m - 1]."""
    return ((x % m) + m) % m


def mod_add(a: int, b: int, m: int = MOD) -> int:
    """Cộng đồng dư: (a + b) mod m."""
    return (mod_norm(a, m) + mod_norm(b, m)) % m


def mod_sub(a: int, b: int, m: int = MOD) -> int:
    """Trừ đồng dư an toàn: (a - b + m) mod m."""
    return (mod_norm(a, m) - mod_norm(b, m) + m) % m


def mod_mul(a: int, b: int, m: int = MOD) -> int:
    """Nhân đồng dư: (a * b) mod m."""
    return (mod_norm(a, m) * mod_norm(b, m)) % m


if __name__ == "__main__":
    # Test 1: Chuẩn hóa số âm -7 khi chia lấy dư cho 3 (kết quả chuẩn = 2)
    print(f"Norm(-7, 3): {mod_norm(-7, 3)}")

    # Test 2: Cộng, trừ, nhân hai số lớn sát ngưỡng 10^9 + 7
    a = 1_000_000_005  # Đồng dư với -2 (mod 10^9 + 7)
    b = 1_000_000_006  # Đồng dư với -1 (mod 10^9 + 7)
    print(f"Add: {mod_add(a, b)} | Sub: {mod_sub(a, b)} | Mul: {mod_mul(a, b)}")

    # Test 3: Tính biểu thức (10^9 * 10^9 - 100) mod (10^9 + 7)
    tich = mod_mul(1_000_000_000, 1_000_000_000)
    print(f"Expr: {mod_sub(tich, 100)}")

#include <iostream>
using namespace std;

const long long MOD = 1'000'000'007LL;

// Lũy thừa nhị phân tính a^b % m trong O(log b)
long long luy_thua_mod(long long a, long long b, long long m = MOD) {
    long long res = 1;
    a %= m;
    while (b > 0) {
        if (b & 1) res = (res * a) % m;
        a = (a * a) % m;
        b >>= 1;
    }
    return res;
}

// Nghịch đảo modulo của b theo số nguyên tố m (Định lý Fermat nhỏ: b^(m-2) % m)
long long nghich_dao_mod(long long b, long long m = MOD) {
    return luy_thua_mod(b, m - 2, m);
}

// Tính tổ hợp C(n, k) % MOD = n! / (k! * (n - k)!) % MOD
long long to_hop_mod(int n, int k) {
    if (k < 0 || k > n) return 0;
    long long tu = 1, mau = 1;
    for (int i = 1; i <= n; ++i) tu = (tu * i) % MOD;
    for (int i = 1; i <= k; ++i) mau = (mau * i) % MOD;
    for (int i = 1; i <= n - k; ++i) mau = (mau * i) % MOD;
    return (tu * nghich_dao_mod(mau, MOD)) % MOD;
}

int main() {
    // Test 1: Chia đồng dư (36 / 12) mod 7 thông qua nghịch đảo của 12 mod 7 (tức 5^-1 mod 7 = 3)
    long long a_mod = 36 % 7;                 // 1
    long long b_inv = nghich_dao_mod(12, 7);  // 5^(7-2) % 7 = 3
    cout << "DivMod(36/12, 7): " << (a_mod * b_inv) % 7 << "\n";

    // Test 2: Tổ hợp C(10, 3) % (10^9 + 7) = 120
    cout << "C(10, 3): " << to_hop_mod(10, 3) << "\n";

    // Test 3: Tổ hợp lớn C(100, 50) % (10^9 + 7) = 538992043
    cout << "C(100, 50): " << to_hop_mod(100, 50) << "\n";

    return 0;
}

MOD = 1_000_000_007


def luy_thua_mod(a: int, b: int, m: int = MOD) -> int:
    """Lũy thừa nhị phân tính a^b % m trong O(log b)."""
    return pow(a, b, m)


def nghich_dao_mod(b: int, m: int = MOD) -> int:
    """Nghịch đảo modulo của b theo số nguyên tố m: b^(m-2) % m."""
    return luy_thua_mod(b, m - 2, m)


def to_hop_mod(n: int, k: int) -> int:
    """Tính tổ hợp C(n, k) % MOD = n! * (k! * (n - k)!)^(MOD - 2) % MOD."""
    if k < 0 or k > n:
        return 0
    tu, mau = 1, 1
    for i in range(1, n + 1):
        tu = (tu * i) % MOD
    for i in range(1, k + 1):
        mau = (mau * i) % MOD
    for i in range(1, n - k + 1):
        mau = (mau * i) % MOD
    return (tu * nghich_dao_mod(mau, MOD)) % MOD


if __name__ == "__main__":
    # Test 1: Chia đồng dư (36 / 12) mod 7 thông qua nghịch đảo của 12 mod 7
    a_mod = 36 % 7                 # 1
    b_inv = nghich_dao_mod(12, 7)  # 5^(7-2) % 7 = 3
    print(f"DivMod(36/12, 7): {(a_mod * b_inv) % 7}")

    # Test 2: Tổ hợp C(10, 3) % (10^9 + 7) = 120
    print(f"C(10, 3): {to_hop_mod(10, 3)}")

    # Test 3: Tổ hợp lớn C(100, 50) % (10^9 + 7) = 538992043
    print(f"C(100, 50): {to_hop_mod(100, 50)}")