AtCoder.Internal.Math

Internal math implementation.

Example

>>> import AtCoder.Internal.Math
>>> powMod 10 60 998244353 -- 10^60 mod 998244353
526662729

>>> isPrime 998244353
True

>>> isPrime 4
False

>>> invGcd 128 37
(1,24)

>>> 24 * 128 `mod` 37 == 1
True

>>> primitiveRoot 2130706433
3

>>> floorSumUnsigned 8 12 3 5
6

Since: 1.0.0.0

Documentation

powMod

Arguments

:: HasCallStack

=> Int

$x$

-> Int

$n$

-> Int

$m$

-> Int

$x^n \bmod m$

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

isPrime :: Int -> Bool

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

invGcd :: Int -> Int -> (Int, Int)

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

primitiveRoot :: Int -> Int

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

floorSumUnsigned :: Int -> Int -> Int -> Int -> Int

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