|
cai_lw's competitive programming library
|
|
| |
|
cai_lw's competitive programming library
|
|
|
| |
Classes | |
| class | cplib::BarrettModInt< Context > |
| Modular integer using Barrett reduction. More... | |
| class | cplib::ModInt2P61M1 |
| Modular integer modulo \(N=2^{61}-1\), a Mersenne prime. More... | |
| class | cplib::MontgomeryModInt< Context > |
| Modular integer stored in Montgomery form. More... | |
Functions | |
| template<typename T , std::enable_if_t< std::is_unsigned_v< T > > * = nullptr> | |
| std::optional< T > | cplib::discrete_log (T g, T x, T n) |
| Modular discrete logarithm. | |
| template<typename T , std::enable_if_t< std::is_unsigned_v< T > > * = nullptr> | |
| std::vector< T > | cplib::factorize (T n) |
| Integer factorization. | |
| template<typename T , std::enable_if_t< std::is_unsigned_v< T > > * = nullptr> | |
| constexpr T | cplib::gcd (T x, T y) |
| Greatest common divisor. | |
| template<typename T , std::enable_if_t< std::is_unsigned_v< T > > * = nullptr> | |
| constexpr std::tuple< std::make_signed_t< T >, std::make_signed_t< T >, T > | cplib::bezout (T x, T y) |
| Bézout coefficients, i.e. \((a,b)\) such that \(ax+by=\mathrm{GCD}(x,y)\). | |
| template<typename T , std::enable_if_t< std::is_unsigned_v< T > > * = nullptr> | |
| constexpr T | cplib::mod_inverse (T x, T m) |
| Modular inverse. | |
| template<typename T , typename Op = std::multiplies<T>> | |
| constexpr T | cplib::pow (T base, uint64_t exp, Op &&op={}) |
| A generic exponetiation by squaring function. | |
| template<typename T , std::enable_if_t< std::is_unsigned_v< T > > * = nullptr> | |
| T | cplib::prime_or_factor (T n) |
| Primality test and possibly return a non-trivial factor. | |
| template<typename T , std::enable_if_t< std::is_unsigned_v< T > > * = nullptr> | |
| bool | cplib::is_prime (T n) |
| Primality test. | |
| template<typename T , std::enable_if_t< std::is_unsigned_v< T > > * = nullptr> | |
| T | cplib::primitive_root_prime (T p) |
| Primitive root modulo a prime number. | |
| template<typename T , std::enable_if_t< std::is_unsigned_v< T > > * = nullptr> | |
| std::optional< T > | cplib::primitive_root (T n) |
| Primitive root modulo any number. | |
| template<typename Fp > | |
| std::optional< Fp > | cplib::sqrt_mod_fp (Fp n) |
| Square root modulo a prime number. | |
| template<typename T , std::enable_if_t< std::is_unsigned_v< T > > * = nullptr> | |
| std::optional< T > | cplib::sqrt_mod_prime (T n, T p) |
| Square root modulo a prime number. | |
|
constexpr |
Bézout coefficients, i.e. \((a,b)\) such that \(ax+by=\mathrm{GCD}(x,y)\).
Returns a 3-tuple \((a,b,d)\) such that \(ax+by=d\) where \(d=\mathrm{GCD}(x,y)\). It is guaranteed that either \(|a|\leq\lfloor\frac{y}{2d}\rfloor, |b|\leq\lfloor\frac{x}{2d}\rfloor\) or \((a,b)\in\{(0,0),(0,1),(1,0)\}\). In other words, \((a,b)\) is always the unique solution with both \(|a|\) and \(|b|\) being the smallest.
The above property shows that, for input x and y of an unsigned integer type T, the output a and b can always fit in the signed integer type with the same width as T, i.e. std::make_signed_t<T>. Thus, a and b are returned as such type.
This is implemented using the extended Euclidean algorithm. Various extended binary GCD algorithms exist, but they either cannot guarantee to find a unique or small solution, or are not faster than the extended Euclidean algorithm due to extra bound checks needed for finding a unique or small solution.
| std::optional< T > cplib::discrete_log | ( | T | g, |
| T | x, | ||
| T | n | ||
| ) |
Modular discrete logarithm.
Given integers \(n\geq 1\) and \(0\leq g,x <n\), return the minimum non-negative integer \(k\) such that \(g^k\equiv x\) (mod \(n\)), or std::nullopt if no such \(k\) exists.
Note that if \(x=1\) this function will always return 0. The minimum positive integer \(k\) such that \(g^k\equiv 1\) (mod \(n\)) is called the multiplicative order of \(g\) modulo \(n\), and can be found more efficiently than discrete logarithm.
| std::vector< T > cplib::factorize | ( | T | n | ) |
Integer factorization.
Returns primes factors with multiplicity in ascending order.
After ruling out primes (and possibly finding a non-trivial factor) with prime_or_factor(), it runs Brent's improved version of Pollard's rho algorithm. Time complexity is \(O(N^{1/4})\) expected.
| T | An unsigned integer type. |
|
constexpr |
Greatest common divisor.
std::gcd is available since C++17, but the GCC implementaiton uses the slow Euclidean algorithm until version 11. This implementation uses binary GCD which is generally several times faster.
Note that, unlike std::gcd, this function only accepts unsigned integers.
| bool cplib::is_prime | ( | T | n | ) |
Primality test.
| T | An unsigned integer type. |
|
constexpr |
Modular inverse.
Returns the unique \(y\) such that \(xy\equiv 1\pmod{m}\) and \(0\leq y<m\).
Requires \(\mathrm{GCD}(x,m)=1\). Note that \(m\) does not have to be a prime.
|
constexpr |
A generic exponetiation by squaring function.
| Op | An associative binary operator over T |
| T cplib::prime_or_factor | ( | T | n | ) |
Primality test and possibly return a non-trivial factor.
Always returns 1 if n is prime. Otherwise, may return 0 or a non-trivial factor of n. As most factorization algorithm requires primality test first, a factor found in primality test is work saved for factorization.
In this implementation, after ruling out small prime divisors, Miller-Rabin test is run on a fixed set of \(k\) bases that are known to cover all numbers up to a certain bound, where \(k=3\) covers all 32-bit integers and \(k=7\) covers all 64-bit integers. The time complexity is thus \(O(k\log N)\).
In this implementation, the non-trivial factor may come from one of the following:
n is even.n and product of small odd primes.| T | An unsigned integer type. |
| std::optional< T > cplib::primitive_root | ( | T | n | ) |
Primitive root modulo any number.
For any primitive root \(g\) the minimum positive integer \(k\) that satisfies \(g^k\equiv 1 \pmod{n}\) is \(\phi(n)\) where \(\phi\) is Euler's totient function. Primitive root exists if and only if \(n=2,4,p^k,2p^k\) where \(p\) is an odd prime and \(k\geq 1\). This function returns std::nullopt if it does not exist.
| T | An unsigned integer type. |
| T cplib::primitive_root_prime | ( | T | p | ) |
Primitive root modulo a prime number.
For the given prime \(p\), returns any \(0<g<p\) such that the minimum positive integer \(k\) that satisfies \(g^k\equiv 1 \pmod{p}\) is \(p-1\).
| T | An unsigned integer type. |
| std::optional< Fp > cplib::sqrt_mod_fp | ( | Fp | n | ) |
Square root modulo a prime number.
Returns a \(x\) such that \(x^2\equiv n \pmod{p}\), or std::nullopt if it doesn't exist. \(-x\) is always also a solution and there is no other solution.
This is implemented using Cipolla's algorithm, as the common alternative Tonelli-Shanks algorithm is slow when \(p-1\) is divisible by a high power of 2, which is commonly the case in competitive programming, since this is exactly the requirement for a prime to be FFT-friendly.
| Fp | Finite field \(\mathbb{F}_p\) where \(p\) is prime. |
| std::optional< T > cplib::sqrt_mod_prime | ( | T | n, |
| T | p | ||
| ) |
Square root modulo a prime number.
Returns a \(x\) such that \(x^2\equiv n \pmod{p}\) and \(0\leq x<p\), or std::nullopt if it doesn't exist. If \(x\neq 0\) then \(p-x\) is always also a solution, and there is no other solution.
| T | An unsigned integer type |
1.9.6