Returns \(x^n \bmod m\).

Constraints

• \(0 \le n\)
• \(1 \le m\)

Complexity

• \(O(\log n)\)

Example

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

Since: 1.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

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

crt calculates \(y\) such that \(y \equiv r_i \pmod m_i, \forall i \in \lbrace 0,1,\cdots, n - 1 \rbrace\):

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

The property can be checked as follows:

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

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 calculates the number of points surrounded by a line \(y = \frac {a \times x + b} {m} \) and \(x, y\) axes in \(O(\log m)\) time:

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