Number Theory Optimization

Number theory in contests combines factorization, modular arithmetic, and clever counting on integers with divisibility constraints.

Why this shows up in the real world

Cryptography, competitive programming, and combinatorics lean on primes, residues mod n, and fast arithmetic on huge integers.

Core idea (explained for students)

Read constraints: mod prime? need inverse? counting coprime pairs? Often reduce to gcd, φ, or prime exponent vectors.

Try this in Python

def mod_pow(base: int, exp: int, mod: int) -> int:
    res = 1
    base %= mod
    while exp:
        if exp & 1:
            res = res * base % mod
        base = base * base % mod
        exp >>= 1
    return res


print(mod_pow(2, 1000000000, 1000000007))

Common mistakes

• Brute force over all integers to 10¹².
• Missing gcd feasibility check.
• Wrong mod at output.

Key takeaways

• Factor template checklist: gcd, pow, sieve, CRT.
• Estimate magnitude—if n≤10⁶, sieve; if n≤10¹⁸, math.