AtCoder.Extra.Math

Extra math module.

Since: 1.0.0.0

Re-exports from the internal math module

isPrime32 :: Int -> Bool

\(O(k \log^3 n) (k = 3)\). Returns whether the given Int value is a prime number.

Constraints

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

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

Binary exponentiation

Examples

>>> import AtCoder.Extra.Math qualified as M
>>> import Data.Semigroup (Product(..), Sum(..))
>>> getProduct $ M.power (<>) 32 (Product 2)
4294967296

>>> getProduct $ M.stimes' 32 (Product 2)
4294967296

>>> getProduct $ M.mtimes' 32 (Product 2)
4294967296

power :: (a -> a -> a) -> Int -> a -> a

Calculates \(x^n\) with custom multiplication operator using the binary exponentiation technique.

The internal implementation is taken from Data.Semigroup.stimes, but power uses strict evaluation and is often much faster.

Complexity

• \(O(\log n)\)

Constraints

• \(n \gt 0\)

Since: 1.0.0.0

stimes' :: Semigroup a => Int -> a -> a

Strict variant of Data.Semigroup.stimes.

Complexity

• \(O(\log n)\)

Constraints

• \(n \gt 0\)

Since: 1.0.0.0

mtimes' :: Monoid a => Int -> a -> a

Strict variant of Data.Monoid.mtimes.

Complexity

• \(O(\log n)\)

Constraints

• \(n \ge 0\)

Since: 1.0.0.0