| Safe Haskell | None |
|---|---|
| Language | GHC2021 |
AtCoder.Extra.Math
Description
Extra math module.
Since: 1.0.0.0
Synopsis
- primes :: HasCallStack => Int -> Vector Int
- isPrime :: HasCallStack => Int -> Bool
- primeFactors :: HasCallStack => Int -> Vector (Int, Int)
- primeFactorsUnsorted :: HasCallStack => Int -> Vector (Int, Int)
- divisors :: HasCallStack => Int -> Vector Int
- divisorsUnsorted :: HasCallStack => Int -> Vector Int
- primitiveRoot :: HasCallStack => Int -> Int
- power :: HasCallStack => (a -> a -> a) -> Int -> a -> a
- stimes' :: (HasCallStack, Semigroup a) => Int -> a -> a
- mtimes' :: (HasCallStack, Monoid a) => Int -> a -> a
Prime numbers and divisors
primes :: HasCallStack => 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.
Example
>>>primes 100[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]
Since: 1.2.6.0
isPrime :: HasCallStack => 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}\).
Example
>>>isPrime 100055128505716009True
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\)
Example
>>>primeFactors 180[(2,2),(3,2),(5,1)]
>>>primeFactors 123123123123123123[(3,2),(7,1),(11,1),(13,1),(19,1),(41,1),(52579,1),(333667,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 :: HasCallStack => Int -> Vector Int Source #
Enumerates divisors of the input value.
Constraints
- \(x \ge 1\)
Example
>>>divisors 180[1,2,3,4,5,6,9,10,12,15,18,20,30,36,45,60,90,180]
Since: 1.2.6.0
divisorsUnsorted :: HasCallStack => Int -> Vector Int Source #
Enumerates divisors of the input value, not sorted.
Constraints
- \(x \ge 1\)
Example
>>>divisorsUnsorted 180[1,2,4,3,6,12,9,18,36,5,10,20,15,30,60,45,90,180]
Since: 1.2.6.0
PrimitiveRoot
primitiveRoot :: HasCallStack => Int -> Int Source #
Returns a primitive root modulo \(p\), where \(p\) is a prime number.
Constraints
- \(p\) must be a prime number.
Example
>>>primitiveRoot 999999999999999989833278905416200545
>>>primitiveRoot 10005512850571600940765942246299710
Since: 1.2.7.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 :: HasCallStack => (a -> a -> a) -> Int -> a -> a Source #
Calculates \(f^n(x)\) 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