Expand description
Number-theoretic utilities for contest problems.
Modules§
- fft
- The Fast Fourier Transform (FFT) and Number Theoretic Transform (NTT)
- num
- Rational and Complex numbers, safe modular arithmetic, and linear algebra, implemented minimally for contest use. If you need more features, you might be interested in crates.io/crates/num
Functions§
- canon_
egcd - Assuming a != 0, finds smallest coef_b >= 0 such that a * coef_a + b * coef_b = c.
- extended_
gcd - Finds (d, coef_a, coef_b) such that d = gcd(a, b) = a * coef_a + b * coef_b.
- factorize
- Assuming x >= 1, finds the prime factorization of n TODO: pollard_rho needs randomization to ensure correctness in contest settings!
- is_
prime - Assuming x >= 0, returns whether x is prime