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

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.

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