Math
It contains number-theoretic algorithms.
pow_mod
ll pow_mod(ll x, ll n, int m)
It returns $x^n \bmod m$.
Constraints
- $0 \le n$
- $1 \le m$
Complexity
- $O(\log n)$
inv_mod
ll inv_mod(ll x, ll m)
It returns an integer $y$ such that $0 \le y < m$ and $xy \equiv 1 \pmod m$.
Constraints
- $\gcd(x, m) = 1$
- $1 \leq m$
Complexity
- $O(\log m)$
crt
pair<ll, ll> crt(vector<ll> r, vector<ll> m)
Given two arrays $r,m$ with length $n$, it solves the modular equation system
$$x \equiv r[i] \pmod{m[i]}, \forall i \in \lbrace 0,1,\cdots, n - 1 \rbrace.$$
If there is no solution, it returns $(0, 0)$. Otherwise, all the solutions can be written as the form $x \equiv y \pmod z$, using integers $y, z$ $(0 \leq y < z = \mathrm{lcm}(m[i]))$. It returns this $(y, z)$ as a pair. If $n=0$, it returns $(0, 1)$.
Constraints
- $|r| = |m|$
- $1 \le m[i]$
- $\mathrm{lcm}(m[i])$ is in
ll.
Complexity
- $O(n \log{\mathrm{lcm}(m[i])})$
floor_sum
ll floor_sum(ll n, ll m, ll a, ll b)
It returns $\sum_{i = 0}^{n - 1} \mathrm{floor}(\frac{a \times i + b}{m})$.
Constraints
- $0 \leq n \leq 10^9$
- $1 \leq m \leq 10^9$
- $0 \leq a, b \lt m$
Complexity
- $O(\log{(n+m+a+b)})$
Examples
AC code of https://atcoder.jp/contests/practice2/tasks/practice2_c