Processing math: 23%
ac-library-hs-1.2.0.0: Data structures and algorithms
Safe HaskellSafe-Inferred
LanguageGHC2021

AtCoder.Extra.Math

Description

Extra math module.

Since: 1.0.0.0

Synopsis

Re-exports from the internal math module

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

O(klog3n)(k=3). Returns whether the given Int value is a prime number.

Constraints

  • n<4759123141(232<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