Overview

Provides implementations and guidance for common number theory algorithms used in competitive programming, from modular arithmetic to FFT/NTT and sieves. It covers modular exponentiation, inverses, CRT, linear Diophantine equations, and prime generation to help you solve problems faster.

How This Skill Works

The skill categorizes core algorithms into modular arithmetic, gcd and extensions, CRT, FFT/NTT, and sieves, offering ready-to-use templates and parameter guidance. You can select an algorithm, supply inputs via the provided schema (algorithm, parameters, language, modulo), and apply the appropriate method to your CP problem.

When to Use It

• Need fast modular exponentiation (a^b mod m) for large exponents.
• Want to compute modular inverses or solve linear congruences.
• Combine residues from several moduli with the Chinese Remainder Theorem.
• Require polynomial multiplication under a modulus using FFT/NTT.
• Generate primes or count with a linear sieve for combinatorics problems.

Quick Start

1. Step 1: Identify the needed area (modular arithmetic, CRT, NTT, or sieve).
2. Step 2: Pick language (cpp/python/java) and craft input according to the schema.
3. Step 3: Implement or reuse a template, then test on small and edge cases.

Best Practices

• Use modular exponentiation with binary exponentiation and avoid overflow.
• Prefer Extended GCD or Fermat's little theorem for inverses depending on mod.
• Use CRT for coprime moduli, verify with a reverse check.
• Choose NTT when the modulus supports a primitive root and large transforms.
• Precompute primes, factorials, and inverse factorials when solving counting problems.

Example Use Cases

• Compute a^b mod m in CP problem with huge b.
• Find x such that x ≡ a1 (mod m1) and x ≡ a2 (mod m2).
• Convolve polynomials modulo a prime using NTT for fast counting.
• Solve a linear Diophantine equation ax + by = c in number theory tasks.
• Generate all primes up to N with a linear sieve for counting distinct primes.

Frequently Asked Questions