พื้นฐาน Number Theory

Number Theory (ทฤษฎีจำนวน) เป็นหนึ่งในหัวข้อสำคัญที่พบบ่อยในการแข่งขัน โจทย์หลายข้อต้องใช้ความรู้เรื่องจำนวนเต็ม การหาร และจำนวนเฉพาะ

การหารลงตัว (Divisibility)

จำนวนเต็ม $a$ หารลงตัวด้วย $b$ เขียนแทนด้วย $b \mid a$ หมายความว่า $a = b \times k$ สำหรับจำนวนเต็ม $k$ บางตัว

// ตรวจสอบการหารลงตัว
bool isDivisible(int a, int b) {
    return a % b == 0;
}

Greatest Common Divisor (GCD)

GCD หรือ ห.ร.ม. (หารร่วมมาก) คือจำนวนที่มากที่สุดที่หารทั้งสองจำนวนลงตัว

Euclidean Algorithm

// วิธี Euclidean O(log(min(a,b)))
int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

// หรือใช้ recursion
int gcdRecursive(int a, int b) {
    if (b == 0) return a;
    return gcdRecursive(b, a % b);
}

// C++ มี __gcd และ std::gcd (C++17)
#include <algorithm>
int g = __gcd(12, 18); // 6

หลักการทำงาน

$\gcd(a, b) = \gcd(b, a \mod b)$

ตัวอย่าง: หา $\gcd(48, 18)$

• $\gcd(48, 18) = \gcd(18, 48 \mod 18) = \gcd(18, 12)$
• $\gcd(18, 12) = \gcd(12, 18 \mod 12) = \gcd(12, 6)$
• $\gcd(12, 6) = \gcd(6, 12 \mod 6) = \gcd(6, 0)$
• $\gcd(6, 0) = 6$

Least Common Multiple (LCM)

LCM หรือ ค.ร.น. (คูณร่วมน้อย) คือจำนวนที่น้อยที่สุดที่หารด้วยทั้งสองจำนวนลงตัว

// สูตร: lcm(a, b) = (a * b) / gcd(a, b)
long long lcm(long long a, long long b) {
    return a / __gcd(a, b) * b; // หารก่อนคูณเพื่อป้องกัน overflow
}

// C++17 มี std::lcm
#include <numeric>
long long l = std::lcm(12, 18); // 36

⚠️ Warning: ต้องระวัง overflow เมื่อคูณ $a \times b$ ให้หาร gcd ก่อนคูณ

Extended Euclidean Algorithm

Extended GCD หาค่า $x, y$ ที่ทำให้ $ax + by = \gcd(a, b)$

// คืนค่า gcd และหา x, y ที่ทำให้ ax + by = gcd(a,b)
int extGcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int x1, y1;
    int g = extGcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

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

int x, y;
int g = extGcd(35, 15, x, y);
// g = 5, x = 1, y = -2
// ตรวจสอบ: 35 * 1 + 15 * (-2) = 35 - 30 = 5 ✓

การแยกตัวประกอบ (Factorization)

Trial Division

// หาตัวประกอบเฉพาะทั้งหมด O(sqrt(n))
vector<pair<int, int>> factorize(int n) {
    vector<pair<int, int>> factors;
    
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            int count = 0;
            while (n % i == 0) {
                n /= i;
                count++;
            }
            factors.push_back({i, count});
        }
    }
    
    if (n > 1) {
        factors.push_back({n, 1});
    }
    
    return factors;
}

// ตัวอย่าง: factorize(60)
// คืน: [(2, 2), (3, 1), (5, 1)]
// 60 = 2² × 3 × 5

จำนวนตัวหาร (Number of Divisors)

ถ้า $n = p_1^{a_1} \times p_2^{a_2} \times ... \times p_k^{a_k}$

จำนวนตัวหารของ $n$ คือ $(a_1 + 1)(a_2 + 1)...(a_k + 1)$

int countDivisors(int n) {
    int count = 1;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            int exp = 0;
            while (n % i == 0) {
                n /= i;
                exp++;
            }
            count *= (exp + 1);
        }
    }
    if (n > 1) count *= 2;
    return count;
}

ผลรวมตัวหาร (Sum of Divisors)

$\sigma(n) = \prod_{i=1}^{k} \frac{p_i^{a_i+1} - 1}{p_i - 1}$

long long sumDivisors(int n) {
    long long sum = 1;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            long long p = i;
            long long term = 1;
            while (n % i == 0) {
                n /= i;
                term = term * p + 1;
            }
            sum *= term;
        }
    }
    if (n > 1) sum *= (1 + n);
    return sum;
}

หาตัวหารทั้งหมด

// O(sqrt(n))
vector<int> getDivisors(int n) {
    vector<int> divisors;
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            divisors.push_back(i);
            if (i != n / i) {
                divisors.push_back(n / i);
            }
        }
    }
    sort(divisors.begin(), divisors.end());
    return divisors;
}

// ตัวอย่าง: getDivisors(12)
// คืน: [1, 2, 3, 4, 6, 12]

Euler’s Totient Function (φ)

$\phi(n)$ คือจำนวนของจำนวนเต็มบวกที่น้อยกว่าหรือเท่ากับ $n$ และเป็น coprime กับ $n$ (gcd = 1)

สูตร

$\phi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right)$

int phi(int n) {
    int result = n;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            while (n % i == 0) n /= i;
            result -= result / i;
        }
    }
    if (n > 1) result -= result / n;
    return result;
}

คุณสมบัติสำคัญ

• $\phi(1) = 1$
• $\phi(p) = p - 1$ สำหรับจำนวนเฉพาะ $p$
• $\phi(p^k) = p^{k-1}(p - 1)$
• $\phi(ab) = \phi(a)\phi(b)$ เมื่อ $\gcd(a, b) = 1$

ตัวอย่างโจทย์

โจทย์: หาจำนวนคู่ (i, j) ที่ gcd(i, j) = 1

// ให้ n หาจำนวนคู่ (i, j) ที่ 1 ≤ i < j ≤ n และ gcd(i, j) = 1
long long countCoprimePairs(int n) {
    long long count = 0;
    for (int i = 1; i <= n; i++) {
        count += phi(i);
    }
    return count - 1; // ลบคู่ (1, 1)
}

สรุป

Function	สูตร/วิธี	Complexity
GCD	Euclidean	$O(\log n)$
LCM	$\frac{a \times b}{\gcd(a,b)}$	$O(\log n)$
Factorization	Trial Division	$O(\sqrt{n})$
Count Divisors	$(a_1+1)(a_2+1)...$	$O(\sqrt{n})$
Euler’s φ	$n\prod(1-\frac{1}{p})$	$O(\sqrt{n})$

💡 Tip: ใน C++ สามารถใช้ __gcd() สำหรับ GCD และ std::lcm() (C++17) สำหรับ LCM ได้เลย