Returns $x^n \bmod m$.

Constraints

• $0 \le n$
• $1 \le m \lt 2^{31}$

Complexity

• $O(\log n)$

Example

>>> let m = 998244353
>>> powMod 10 60 m -- 10^60 mod m
526662729

Since: 1.0.0.0

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)$

Example

>>> let m = 998244353
>>> (invMod 2 m) * 2 `mod` m -- (2^(-1) mod m) * 2 mod m
1

Since: 1.0.0.0

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 Int bounds.

Complexity

• $O(n \log{\mathrm{lcm}(m[i])})$

Example

>>> import Data.Vector.Unboxed qualified as VU
>>> let rs = VU.fromList @Int [6, 7, 8, 9]
>>> let ms = VU.fromList @Int [2, 3, 4, 5]
>>> crt rs ms
(4,60)

>>> let (y, {- lcm ms -} _) = crt rs ms
>>> VU.zipWith mod rs ms
[0,1,0,4]

>>> VU.zipWith mod rs ms == VU.map (y `mod`) ms
True

Since: 1.0.0.0

Returns $\sum\limits_{i = 0}^{n - 1} \left\lfloor \frac{a \times i + b}{m} \right\rfloor$.

Constraints

• $0 \le n$
• $1 \le m$

Complexity

• $O(\log m)$

Example

>>> floorSum 5 1 1 1 -- floorSum n {- line information -} m a b
15

  y
  ^
6 |
5 |           o           line: y = x + 1
4 |        o  o           The number of `o` is 15
3 |     o  o  o
2 |  o  o  o  o
1 |  o  o  o  o
--+-----------------> x
  0  1  2  3  4  5
                 n = 5

Since: 1.0.0.0