Safe Haskell	None
Language	GHC2021

AtCoder.Internal.Math

Description

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

Synopsis

powMod :: HasCallStack => Int -> Int -> Int -> Int
isPrime :: Int -> Bool
invGcd :: Int -> Int -> (Int, Int)
primitiveRoot :: Int -> Int
floorSumUnsigned :: Int -> Int -> Int -> Int -> Int

Documentation

powMod :: HasCallStack => Int -> Int -> Int -> Int #

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

isPrime :: Int -> Bool #

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

Since: 1.0.0

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

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

Constraints

\(1 \le b\) (not asserted)

Since: 1.0.0

primitiveRoot :: Int -> Int #

Returns primitive root.

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