数論的アルゴリズム詰め合わせです。
ll pow_mod(ll x, ll n, int m)
@{keyword.constraints}
$0 \le n$ $1 \le m$
@{keyword.complexity}
$O(\log n)$
ll inv_mod(ll x, ll m)
@{keyword.constraints}
$\gcd(x, m) = 1$ $1 \leq m$
@{keyword.complexity}
$O(\log m)$
pair<ll, ll> crt(vector<ll> r, vector<ll> m)
同じ長さの配列
を解きます。答えは(存在するならば)
@{keyword.constraints}
$|r| = |m|$ $1 \le m[i]$ -
$\mathrm{lcm}(m[i])$ がll
に収まる。
@{keyword.complexity}
$O(n \log{\mathrm{lcm}(m[i])})$
ll floor_sum(ll n, ll m, ll a, ll b)
を返します。答えがオーバーフローしたならば
@{keyword.constraints}
$0 \leq n \lt 2^{32}$ $1 \leq m \lt 2^{32}$
@{keyword.complexity}
$O(\log m)$
@{example.floor_sum_practice}