Modular Arithmetic

ในการแข่งขัน Competitive Programming มักพบโจทย์ที่คำตอบมีขนาดใหญ่มาก จึงต้องให้คำตอบเป็น “mod $10^9 + 7$” หรือค่าอื่นๆ

พื้นฐาน Modulo

การ mod คือการหาเศษจากการหาร

$a \mod m = r$ หมายความว่า $a = qm + r$ โดย $0 \leq r < m$

const int MOD = 1e9 + 7;

int mod(int x) {
    return ((x % MOD) + MOD) % MOD;
}

⚠️ สำคัญ: ใน C++ การ mod จำนวนลบอาจได้ค่าลบ เช่น -7 % 5 = -2 ต้องบวก MOD กลับ

คุณสมบัติของ Modular Arithmetic

การบวกและลบ

$(a + b) \mod m = ((a \mod m) + (b \mod m)) \mod m$ $(a - b) \mod m = ((a \mod m) - (b \mod m) + m) \mod m$

long long addMod(long long a, long long b) {
    return ((a % MOD) + (b % MOD)) % MOD;
}

long long subMod(long long a, long long b) {
    return ((a % MOD) - (b % MOD) + MOD) % MOD;
}

การคูณ

$(a \times b) \mod m = ((a \mod m) \times (b \mod m)) \mod m$

long long mulMod(long long a, long long b) {
    return ((a % MOD) * (b % MOD)) % MOD;
}

การหาร (ต้องใช้ Modular Inverse)

$\frac{a}{b} \mod m = (a \times b^{-1}) \mod m$

โดย $b^{-1}$ คือ modular inverse ของ $b$

Modular Exponentiation

การยกกำลังแบบ mod อย่างมีประสิทธิภาพ

Binary Exponentiation

คำนวณ $a^n \mod m$ ใน $O(\log n)$

long long power(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    
    while (exp > 0) {
        if (exp & 1) { // exp เป็นเลขคี่
            result = (result * base) % mod;
        }
        base = (base * base) % mod;
        exp >>= 1; // exp /= 2
    }
    
    return result;
}

หลักการ

• ถ้า $n = 0$: ผลลัพธ์ = $1$
• ถ้า $n$ เป็นเลขคู่: $a^n = (a^{n/2})^2$
• ถ้า $n$ เป็นเลขคี่: $a^n = a \times a^{n-1}$

ตัวอย่าง: $2^{10}$

• $2^{10} = (2^5)^2$
• $2^5 = 2 \times (2^2)^2$
• $2^2 = (2^1)^2$
• $2^1 = 2 \times 2^0 = 2$

Modular Inverse

$b^{-1}$ คือจำนวนที่ทำให้ $b \times b^{-1} \equiv 1 \pmod{m}$

วิธีที่ 1: Fermat’s Little Theorem

ถ้า $m$ เป็นจำนวนเฉพาะ:

$b^{-1} \equiv b^{m-2} \pmod{m}$

long long modInverse(long long b, long long mod = MOD) {
    return power(b, mod - 2, mod);
}

// การหาร a / b mod m
long long divMod(long long a, long long b) {
    return mulMod(a, modInverse(b));
}

วิธีที่ 2: Extended Euclidean Algorithm

ใช้ได้กับ $m$ ทั่วไปที่ $\gcd(b, m) = 1$

long long extGcd(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1; y = 0;
        return a;
    }
    long long x1, y1;
    long long g = extGcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

long long modInverseExt(long long b, long long mod = MOD) {
    long long x, y;
    extGcd(b, mod, x, y);
    return (x % mod + mod) % mod;
}

วิธีที่ 3: Pre-compute Inverse 1 ถึง n

const int MAXN = 1e6 + 5;
long long inv[MAXN];

void precomputeInverse(int n) {
    inv[1] = 1;
    for (int i = 2; i <= n; i++) {
        inv[i] = (MOD - (MOD / i) * inv[MOD % i] % MOD) % MOD;
    }
}

Factorial และ Combinations

Pre-compute Factorial

const int MAXN = 1e6 + 5;
long long fact[MAXN], invFact[MAXN];

void precompute() {
    fact[0] = 1;
    for (int i = 1; i < MAXN; i++) {
        fact[i] = (fact[i-1] * i) % MOD;
    }
    
    invFact[MAXN-1] = modInverse(fact[MAXN-1]);
    for (int i = MAXN-2; i >= 0; i--) {
        invFact[i] = (invFact[i+1] * (i+1)) % MOD;
    }
}

Binomial Coefficient (nCr)

$\binom{n}{r} = \frac{n!}{r!(n-r)!}$

long long nCr(int n, int r) {
    if (r < 0 || r > n) return 0;
    return (fact[n] * invFact[r] % MOD) * invFact[n-r] % MOD;
}

Lucas’ Theorem

สำหรับคำนวณ $\binom{n}{r} \mod p$ เมื่อ $n$ มีขนาดใหญ่มากและ $p$ เป็นจำนวนเฉพาะ

$\binom{n}{r} \equiv \prod_{i=0}^{k} \binom{n_i}{r_i} \pmod{p}$

โดย $n = \sum_{i} n_i p^i$ และ $r = \sum_{i} r_i p^i$

long long lucas(long long n, long long r, long long p) {
    if (r == 0) return 1;
    return (lucas(n / p, r / p, p) * nCr(n % p, r % p)) % p;
}

ตัวอย่างการใช้งาน

โจทย์: หา $2^{1000000000} \mod (10^9 + 7)$

int main() {
    long long n = 1000000000;
    cout << power(2, n, MOD) << endl;
    return 0;
}

โจทย์: หาจำนวนวิธีเลือกของ r ชิ้นจาก n ชิ้น

int main() {
    precompute();
    int n = 100000, r = 50000;
    cout << nCr(n, r) << endl;
    return 0;
}

โจทย์: หา $(a \times b^{-1}) \mod m$

int main() {
    long long a = 10, b = 3;
    long long result = divMod(a, b);
    // result คือค่าที่ทำให้ (result * 3) % MOD == 10
    cout << result << endl;
    return 0;
}

ทำไมต้อง $10^9 + 7$?

1. เป็นจำนวนเฉพาะ - ทำให้หา modular inverse ได้ง่าย
2. พอดี 32-bit - $10^9 + 7 < 2^{30}$
3. คูณกันไม่ล้น 64-bit - $(10^9)^2 < 2^{63}$

สรุป

Operation	Formula	Code
บวก	$(a+b) \mod m$	(a + b) % MOD
ลบ	$(a-b+m) \mod m$	(a - b + MOD) % MOD
คูณ	$(a \times b) \mod m$	(a * b) % MOD
ยกกำลัง	$a^n \mod m$	power(a, n, MOD)
หาร	$a \times b^{-1} \mod m$	a * modInverse(b) % MOD
Inverse	$a^{m-2} \mod m$	power(a, MOD-2, MOD)
nCr	$\frac{n!}{r!(n-r)!} \mod m$	fact[n] * invFact[r] * invFact[n-r]

💡 Tip: Pre-compute factorial และ inverse factorial ไว้ล่วงหน้าถ้าต้องคำนวณ nCr หลายครั้ง