Safe Haskell	Safe-Inferred
Language	GHC2021

AtCoder.Extra.Math

Contents

Re-exports from the internal math module
Binary exponentiation

Description

Extra math module.

Since: 1.0.0.0

Synopsis

isPrime32 :: HasCallStack => Int -> Bool
invGcd :: Int -> Int -> (Int, Int)
primitiveRoot32 :: HasCallStack => Int -> Int
power :: (a -> a -> a) -> Int -> a -> a
stimes' :: Semigroup a => Int -> a -> a
mtimes' :: Monoid a => Int -> a -> a

Re-exports from the internal math module

isPrime32 :: HasCallStack => Int -> Bool Source #

$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) Source #

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

primitiveRoot32 :: HasCallStack => Int -> Int Source #

Returns the primitive root of the given Int.

Constraints

The input must be a prime number.
The input must be less than $2^32$ .

Since: 1.2.0.0

Binary exponentiation

Examples

Expand

>>> 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 Source #

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 Source #

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 Source #

Strict variant of Data.Monoid.mtimes.

Complexity

$O(\log n)$

Constraints

$n \ge 0$

Since: 1.0.0.0

Key	Shortcut
s	Open this search box
esc	Close this search box
↓,ctrl + j	Move down in search results
↑,ctrl + k	Move up in search results
↵	Go to active search result