📄️ Arithmetic
Operators
📄️ Chinese Remainder Theorem
Theorem
📄️ Dirichlet Convolution
If $f , g
📄️ Fast Fourier Transform (FFT)
📄️ Fibonacci Numbers
From the generating function, we have
📄️ Greatest Common Divisor (GCD)
Euclid's Algorithm
📄️ Möbius function
https://codeforces.com/blog/entry/53925
📄️ Integers in Modular Arithmetic
- Iterative modular inverse//codeforces.com/blog/entry/64345?#comment-482502
📄️ Montgomery Space
📄️ Number Theoretic Transform (NTT)
- ModularArithmetic::ModInt ➝ /cp/math/modint
📄️ Number Theory
Euclid's lemma — If a prime p divides the product ab of two integers a and b, then p must divide at least one of those integers a and b.
📄️ Polynomial Arithmetic
- NTT::conv1D ➝ /cp/math/ntt
📄️ Primality Tests
Naive
📄️ Prime Factorization
Naive Algorithm
📄️ Sieve
Sieve of Eratosthenes