Safe Haskell | Safe-Inferred |
---|---|
Language | GHC2021 |
Synopsis
- powMod :: Integral a => a -> Int -> a -> a
- recipMod :: Integral a => a -> a -> a
- extGCD :: Integral a => a -> a -> (a, a, a)
- linearDiophantine :: Integral a => a -> a -> a -> Maybe (a, a)
- crt :: Integral a => (a, a) -> (a, a) -> Maybe (a, a)
- crt' :: Integral a => (a, a) -> (a, a) -> a
- crts :: Integral a => [(a, a)] -> Maybe (a, a)
- garner :: Integral a => [(a, a)] -> a -> a
Documentation
powMod :: Integral a => a -> Int -> a -> a Source #
>>>
powMod 2 0 1000000007
1>>>
powMod 0 0 1000000007
1>>>
powMod 2 1000000005 1000000007
500000004>>>
powMod 2 (-1) 1000000007
500000004>>>
powMod 123456789 998244353 998244353
123456789>>>
powMod (-2) 2 1000000007
4>>>
powMod (-2) 3 1000000007
999999999
recipMod :: Integral a => a -> a -> a Source #
>>>
recipMod 2 1000000007
500000004>>>
recipMod 10 1000000007
700000005>>>
recipMod 0 1000000007
0
\x m -> not (m >= 1) || mod (x * recipMod x m) m == mod (gcd x m) m
+++ OK, passed 100 tests.
extGCD :: Integral a => a -> a -> (a, a, a) Source #
Extended Euclidean algorithm
(x, y, g) = extGCD a b (a * x + b * y = g)
>>>
extGCD 3 5
(2,-1,1)>>>
extGCD 4 6
(-1,1,2)
\a b -> not (a > 0 && b > 0) || let (_, _ , g) = extGCD a b in g == gcd a b
+++ OK, passed 100 tests.
\a b -> not (a > 0 && b > 0) || let (x, y, g) = extGCD a b in a * x + b * y == g
+++ OK, passed 100 tests.
\a b -> not (a > 0 && b > 0) || let (x, y, g) = extGCD a b in abs x <= div b g && abs y <= div a g
+++ OK, passed 100 tests.
linearDiophantine :: Integral a => a -> a -> a -> Maybe (a, a) Source #
Solve a * x + b * y == c
If multiple solutions exists then return the minimum non-negative x
.
If a /= 0, b /= 0, a * x + b * y == c
then a (x - k * b / g) + b * (y + k * a / g) == c
>>>
linearDiophantine 3 5 1
Just (2,-1)>>>
linearDiophantine 3 5 3
Just (1,0)>>>
linearDiophantine 4 6 2
Just (2,-1)>>>
linearDiophantine 4 6 3
Nothing prop> \a b c -> maybe True (\(x, y) -> a * x + b * y == c) $ linearDiophantine a b c +++ OK, passed 100 tests.
crt :: Integral a => (a, a) -> (a, a) -> Maybe (a, a) Source #
Chinese Remainder Theorem
x = r0 (mod m0), x = r1 (mod m1) ==> x (mod (lcm m0 m1))
>>>
crt (10, 20) (10, 30)
Just (10,60)>>>
crt (10, 20) (10, 20)
Just (10,20)>>>
crt (10, 20) (11, 20)
Nothing
crt' :: Integral a => (a, a) -> (a, a) -> a Source #
p0
,p1
are primep0 /= p1
orr0 == r1
>>>
crt' (2,3) (3,5)
8>>>
crt' (3,5) (3,7)
3>>>
crt' (3,7) (3,7)
3