Documentation

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

M. Forisek and J. Jancina, Fast Primality Testing for Integers That Fit into a Machine Word

Constraints

• $n < 4759123141 (2^{32} < 4759123141)$, otherwise the return value can lie (Wikipedia).

Complexity

• $O(k \log^3 n)$, $k = 3$

Since: 1.0.0.0

Returns $(g, x)$ such that $g = \gcd(a, b), \mathrm{xa} \equiv g \pmod b, 0 \le x \le b/g$.

Constraints

• $1 \le b$ (not asserted)

Since: 1.0.0.0

Returns the primitive root of the given Int.

Constraints

• The input must be a prime number.
• The input must be less than $2^31$.

Since: 1.0.0.0

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

Constraints

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

Complexity

• $O(\log m)$

Since: 1.0.0.0