| Safe Haskell | Safe-Inferred |
|---|---|
| Language | GHC2021 |
AtCoder.Extra.Math
Description
Extra math module.
Since: 1.0.0.0
Synopsis
- isPrime32 :: HasCallStack => Int -> Bool
- invGcd :: Int -> Int -> (Int, Int)
- primitiveRoot32 :: HasCallStack => Int -> Int
- primes :: Int -> Vector Int
- isPrime :: Int -> Bool
- primeFactors :: HasCallStack => Int -> Vector (Int, Int)
- primeFactorsUnsorted :: HasCallStack => Int -> Vector (Int, Int)
- divisors :: Int -> Vector Int
- divisorsUnsorted :: Int -> Vector 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
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
Prime numbers and divisors
primes :: Int -> Vector Int Source #
\(O(n \log \log n)\) Creates an array of prime numbers up to the given limit, using Sieve of Eratosthenes.
The minimum computational complexity is \(\Omega(B \log \log B)\), where \(B = 2^{15}\) is the length of segment. This constraint comes from the use of segmented sieve.
Constraints
- The upper limit must be less than or equal to \(2^{30} (\gt 10^9)\), otherwise the returned prime table is incorrect.
Since: 1.2.6.0
isPrime :: Int -> Bool Source #
\(O(w \log^3 n)\) Miller–Rabin primality test, where \(w = 3\) for \(x \lt 2^{32}\) and \(w = 7\) for \(x \ge 3^{32}\).
Since: 1.2.6.0
primeFactors :: HasCallStack => Int -> Vector (Int, Int) Source #
Returns prime factors in run-length encoding \((p_i, n_i)\), sorted by \(p_i\).
Constraints
- \(x \ge 1\)
Since: 1.2.6.0
primeFactorsUnsorted :: HasCallStack => Int -> Vector (Int, Int) Source #
Returns prime factors in run-length encoding \((p_i, n_i)\) in arbitrary order.
It internally uses probabilistic method (Pollard's rho algorithm) and it can actually result in
runtime error, however, the probability is very low and the API does not return Maybe.
Since: 1.2.6.0
divisors :: Int -> Vector Int Source #
Enumerates divisors of the input value.
Constraints
- \(x \ge 1\)
Since: 1.2.6.0
divisorsUnsorted :: Int -> Vector Int Source #
Enumerates divisors of the input value.
Constraints
- \(x \ge 1\)
Since: 1.2.6.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 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