Chapter 7: Basic Number Theory

Number theory problems fall into two extremes:

1. Trivial if you know the formula: write AC code in 3 minutes.
2. Requires the right theorem: without it, you bang your head for hours.

This chapter focuses on the three most practical and frequently appearing tools.

7.1 Euclidean Algorithm: GCD and LCM

7.1.1 GCD

How do you find gcd(a, b)? School-taught long division is slow. Computers use the Euclidean algorithm.

Core idea: gcd(a, b) = gcd(b, a % b). Replace the dividend with the remainder until it becomes zero.

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}
 
// C++17 offers std::gcd (include <numeric>)
// int res = std::gcd(a, b);

7.1.2 LCM

Formula:

$lcm(a, b) = \frac{a \times b}{gcd(a, b)}$

Pitfall: int lcm = a * b / gcd(a, b); might overflow before dividing.

Safe approach: divide before multiplying:

long long lcm(int a, int b) {
    return (1LL * a / gcd(a, b)) * b;
}

7.2 Primes: Testing and Sieving

A prime is divisible only by 1 and itself (1 is not prime, 2 is the smallest prime).

7.2.1 Trial Division

Problem: Determine if N (≤ 10^{12}) is prime.

Idea: Try dividing by numbers from 2 to N−1.

Optimization: Only test up to √N, because divisors come in pairs.

bool isPrime(long long n) {
    if (n < 2) return false;
    for (long long i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

Complexity: O(√N).

7.2.2 Sieve of Eratosthenes

Problem: Enumerate all primes between 1 and N (≤ 10^6).

Running trial division per number gives O(N√N)—too slow.

Idea:

1. Create a boolean array vis, initially assuming every number is prime.
2. Start from 2, mark all multiples (4, 6, 8...) as composite.
3. Move to the next unmarked number (3), mark its multiples (6, 9, 12...).
4. Repeat until √N.

const int MAXN = 1000005;
bool vis[MAXN];
 
void sieve(int n) {
    vis[0] = vis[1] = true;
    for (int i = 2; i * i <= n; i++) {
        if (!vis[i]) {
            for (int j = i * i; j <= n; j += i) {
                vis[j] = true;
            }
        }
    }
}

Complexity: O(N log log N), almost linear. Works easily for N = 10^6.

Advanced: The Euler sieve / linear sieve is O(N) and suitable for N = 10^7, but mastering the classic sieve is enough for now.

7.3 Modular Arithmetic & Fast Power

Many problems require answers mod 10^9 + 7. Why? Because the raw result might have thousands of digits. We store only the remainder.

7.3.1 Modular Rules

Addition, subtraction, and multiplication all commute with modulo.

1. (a + b) % m = ((a % m) + (b % m)) % m
2. (a * b) % m = ((a % m) * (b % m)) % m
3. Subtraction warning: (a - b) % m can be negative in C++ (-2 % 5 == -2). Safe write: ((a - b) % m + m) % m

7.3.2 Fast Power (Binary Exponentiation)

Problem: Compute a^b % m when b might be as large as 10^{18}.

You can’t loop b times. Use exponentiation by squaring.

using ll = long long;
 
ll quick_pow(ll base, ll power, ll mod) {
    ll result = 1;
    while (power > 0) {
        if (power & 1) {
            result = (result * base) % mod;
        }
        base = (base * base) % mod;
        power >>= 1;
    }
    return result;
}

Complexity: O(log b). Even when b = 10^{18}, you only perform ~60 loops.

🧠 Chapter Summary & Practice

Mastering GCD, prime sieves, and fast exponentiation gives you the key to basic number theory problems.

Practice problems:

1. P1029 GCD and LCM (NOIP 2001 entry) on Luogu.
2. P3383 Linear Sieve Template: try the classic sieve first; if it TLEs, learn Euler sieve.
3. P1226 Fast Power Template: run the template above and feel the O(log N) performance.

With basic math under your belt, it is time to learn some low-level magic—bit manipulation. Why do experts do ten lines of logic in one bit trick? Why is 2^{20} written as 1 << 20?