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