CP-Algorithms Library
This documentation is automatically generated by competitive-verifier/competitive-verifier
cp-algo/math/common.hpp
- View this file on GitHub
- Last update: 2025-05-22 14:15:11+02:00
- Include:
#include "cp-algo/math/common.hpp"
Required by
- cp-algo/linalg/frobenius.hpp
- cp-algo/linalg/matrix.hpp
- cp-algo/linalg/vector.hpp
- cp-algo/math/and_convolution.hpp
- cp-algo/math/bigint.hpp
- cp-algo/math/combinatorics.hpp
cp-algo/math/convolution.hpp- cp-algo/math/decimal.hpp
- cp-algo/math/factorials.hpp
- cp-algo/math/fft.hpp
- cp-algo/math/fft64.hpp
- cp-algo/math/fft_simple.hpp
- cp-algo/math/laurent.hpp
- cp-algo/math/multivar.hpp
- cp-algo/math/poly.hpp
- cp-algo/math/poly/impl/div.hpp
- cp-algo/math/poly/impl/euclid.hpp
- cp-algo/number_theory.hpp
- cp-algo/number_theory/discrete_log.hpp
- cp-algo/number_theory/discrete_sqrt.hpp
- cp-algo/number_theory/euler.hpp
- cp-algo/number_theory/factorize.hpp
- cp-algo/number_theory/modint.hpp
- cp-algo/number_theory/primality.hpp
- cp-algo/number_theory/two_squares.hpp
Verified with
- Addition of Big Integers (verify/bigint/addition.test.cpp)
- Division of Big Integers (verify/bigint/divmod.test.cpp)
- Addition of Hex Big Integers (verify/bigint/hex_addition.test.cpp)
- Division of Hex Big Integers (verify/bigint/hex_divmod.test.cpp)
- Multiplication of Hex Big Integers (verify/bigint/hex_multiplication.test.cpp)
- Multiplication of Big Integers (verify/bigint/multiplication.test.cpp)
- Binomial Coefficient (Prime Mod) (verify/combi/binom.test.cpp)
- Many Factorials (verify/combi/many_facts.test.cpp)
- Many Factorials (dynamic Mod) (verify/combi/many_facts_dynamic.test.cpp)
- Adjugate Matrix (verify/linalg/adj.test.cpp)
- Characteristic Polynomial (verify/linalg/characteristic.test.cpp)
- Matrix Determinant (verify/linalg/det.test.cpp)
- Counting Eulerian Circuits (verify/linalg/euler_circs.test.cpp)
- Inverse Matrix (verify/linalg/inv.test.cpp)
- Matching on General Graph (verify/linalg/matching.test.cpp)
- Pow of Matrix (verify/linalg/pow.test.cpp)
- Pow of Matrix (Frobenius) (verify/linalg/pow_fast.test.cpp)
- Matrix Product (verify/linalg/prod.test.cpp)
- Matrix Product (dynamic modint) (verify/linalg/prod_dynamic_modint.test.cpp)
- Rank of Matrix (verify/linalg/rank.test.cpp)
- Counting Spanning Trees (Directed) (verify/linalg/spanning_directed.test.cpp)
- Counting Spanning Trees (Undirected) (verify/linalg/spanning_undirected.test.cpp)
- System of Linear Equations (verify/linalg/system.test.cpp)
- Matching on General Graph (Tutte matrix) (verify/linalg/tutte.test.cpp)
- Bitwise And Convolution (verify/math/and_convolution.test.cpp)
- Bitwise Xor Convolution (verify/math/xor_convolution.test.cpp)
- Dirichlet Inverse and Prefix Sums (verify/number_theory/dirichlet_inv.test.cpp)
- Dirichlet Convolution and Prefix Sums (verify/number_theory/dirichlet_mul.test.cpp)
- Discrete Logarithm (verify/number_theory/discrete_log.test.cpp)
- Factorize (verify/number_theory/factorize.test.cpp)
- Sqrt Mod (verify/number_theory/modsqrt.test.cpp)
- Primality Test (verify/number_theory/primality.test.cpp)
- Primitive Root (verify/number_theory/primitive_root.test.cpp)
- Sum of Totient Function (verify/number_theory/totient_sum.test.cpp)
- Represent A Number As Two Square Sum (verify/number_theory/two_squares.test.cpp)
- Bell Number (verify/poly/bell.test.cpp)
- Convolution mod $10^9+7$ (verify/poly/convolution107.test.cpp)
- Convolution (Mod $2^{64}$) (verify/poly/convolution64.test.cpp)
- Convolution (Large) (verify/poly/convolution_large.test.cpp)
- Convolution on the Multiplicative Monoid of $\mathbb Z/p\mathbb{Z}$ (verify/poly/convolution_mul.test.cpp)
- Division of Polynomials (verify/poly/div.test.cpp)
- Exp of Power Series (verify/poly/exp.test.cpp)
- Find Linear Recurrence (verify/poly/find_linrec.test.cpp)
- Polynomial Interpolation (verify/poly/inter.test.cpp)
- Polynomial Interpolation (Geometric Sequence) (verify/poly/inter_geo.test.cpp)
- Inv of Power Series (verify/poly/inv.test.cpp)
- Inv of Polynomials (verify/poly/inv_mod.test.cpp)
- Consecutive Terms of Linear Recursion (verify/poly/linrec_consecutive.test.cpp)
- Kth term of Linearly Recurrent Sequence (verify/poly/linrec_single.test.cpp)
- Log of Power Series (verify/poly/log.test.cpp)
- Multipoint Evaluation (verify/poly/multieval.test.cpp)
- Multipoint Evaluation (Geometric Sequence) (verify/poly/multieval_geo.test.cpp)
- Multidimensional Convolution (Truncated) (verify/poly/multivar.test.cpp)
- Conversion to Newton Basis (verify/poly/newton.test.cpp)
- Pow of Power Series (verify/poly/pow.test.cpp)
- Product of Polynomial Sequence (verify/poly/prod_sequence.test.cpp)
- Polynomial Root Finding (verify/poly/roots.test.cpp)
- Shift of Sampling Points of Polynomial (verify/poly/sampling.test.cpp)
- Sqrt of Power Series (verify/poly/sqrt.test.cpp)
- $\sum\limits_{i=0}^\infty r^i i^d$ (verify/poly/sum_exp_poly.test.cpp)
- Polynomial Taylor Shift (verify/poly/taylor.test.cpp)
- Range Affine Range Sum (verify/structures/segtree/range_affine_range_sum.test.cpp)
- Dynamic Range Affine Range Sum (verify/structures/treap/dynamic_sequence_range_affine_range_sum.test.cpp)
Code
#ifndef CP_ALGO_MATH_COMMON_HPP
#define CP_ALGO_MATH_COMMON_HPP
#include <functional>
#include <cstdint>
#include <cassert>
namespace cp_algo::math {
#ifdef CP_ALGO_MAXN
const int maxn = CP_ALGO_MAXN;
#else
const int maxn = 1 << 19;
#endif
const int magic = 64; // threshold for sizes to run the naive algo
auto bpow(auto const& x, auto n, auto const& one, auto op) {
if(n == 0) {
return one;
} else {
auto t = bpow(x, n / 2, one, op);
t = op(t, t);
if(n % 2) {
t = op(t, x);
}
return t;
}
}
auto bpow(auto x, auto n, auto ans) {
return bpow(x, n, ans, std::multiplies{});
}
template<typename T>
T bpow(T const& x, auto n) {
return bpow(x, n, T(1));
}
inline constexpr auto inv2(auto x) {
assert(x % 2);
std::make_unsigned_t<decltype(x)> y = 1;
while(y * x != 1) {
y *= 2 - x * y;
}
return y;
}
}
#endif // CP_ALGO_MATH_COMMON_HPP
#line 1 "cp-algo/math/common.hpp"
#include <functional>
#include <cstdint>
#include <cassert>
namespace cp_algo::math {
#ifdef CP_ALGO_MAXN
const int maxn = CP_ALGO_MAXN;
#else
const int maxn = 1 << 19;
#endif
const int magic = 64; // threshold for sizes to run the naive algo
auto bpow(auto const& x, auto n, auto const& one, auto op) {
if(n == 0) {
return one;
} else {
auto t = bpow(x, n / 2, one, op);
t = op(t, t);
if(n % 2) {
t = op(t, x);
}
return t;
}
}
auto bpow(auto x, auto n, auto ans) {
return bpow(x, n, ans, std::multiplies{});
}
template<typename T>
T bpow(T const& x, auto n) {
return bpow(x, n, T(1));
}
inline constexpr auto inv2(auto x) {
assert(x % 2);
std::make_unsigned_t<decltype(x)> y = 1;
while(y * x != 1) {
y *= 2 - x * y;
}
return y;
}
}
#ifndef CP_ALGO_MATH_COMMON_HPP
#define CP_ALGO_MATH_COMMON_HPP
#include <functional>
#include <cstdint>
#include <cassert>
namespace cp_algo::math{
#ifdef CP_ALGO_MAXN
const int maxn=CP_ALGO_MAXN;
#else
const int maxn=1<<19;
#endif
const int magic=64;auto bpow(auto const&x,auto n,auto const&one,auto op){if(n==0){return one;}else{auto t=bpow(x,n/2,one,op);t=op(t,t);if(n%2){t=op(t,x);}return t;}}auto bpow(auto x,auto n,auto ans){return bpow(x,n,ans,std::multiplies{});}template<typename T>T bpow(T const&x,auto n){return bpow(x,n,T(1));}inline constexpr auto inv2(auto x){assert(x%2);std::make_unsigned_t<decltype(x)>y=1;while(y*x!=1){y*=2-x*y;}return y;}}
#endif
#line 1 "cp-algo/math/common.hpp"
#include <functional>
#include <cstdint>
#include <cassert>
namespace cp_algo::math{
#ifdef CP_ALGO_MAXN
const int maxn=CP_ALGO_MAXN;
#else
const int maxn=1<<19;
#endif
const int magic=64;auto bpow(auto const&x,auto n,auto const&one,auto op){if(n==0){return one;}else{auto t=bpow(x,n/2,one,op);t=op(t,t);if(n%2){t=op(t,x);}return t;}}auto bpow(auto x,auto n,auto ans){return bpow(x,n,ans,std::multiplies{});}template<typename T>T bpow(T const&x,auto n){return bpow(x,n,T(1));}inline constexpr auto inv2(auto x){assert(x%2);std::make_unsigned_t<decltype(x)>y=1;while(y*x!=1){y*=2-x*y;}return y;}}