blob: 24609f0fb074bf6bd70f7266c83799812a9e2352 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
|
module Main where
import Input
egcd :: Integer -> Integer -> (Integer, Integer, Integer)
egcd m n = go 1 0 m 0 1 n
where
go a1 b1 r1 _ _ 0 = (r1, a1, b1)
go a1 b1 r1 a2 b2 r2 =
let (q, r) = r1 `divMod` r2
in go a2 b2 r2 (a1 - q * a2) (b1 - q * b2) r
-- multiplicative inverse of k mod n
multinv :: Integer -> Integer -> Integer
multinv k n =
let (1, x, _) = egcd k n -- x * k + y * n = 1 => x * k = 1 mod n
in x
-- Affine multiplier addend modulus
data Affine = Affine Integer Integer Integer
deriving (Show)
instance Semigroup Affine where
Affine a1 b1 m1 <> Affine a2 b2 m2
| m1 == m2 = Affine ((a1 * a2) `mod` m1) ((a1 * b2 + b1) `mod` m1) m1
| otherwise = error "<>'ing incompatible Affine's"
apply :: Affine -> Integer -> Integer
apply (Affine a b m) x = (a * x + b) `mod` m
inverse :: Affine -> Affine
inverse (Affine a b m) = Affine (multinv a m) 0 m <> Affine 1 (-b) m
power :: Semigroup m => m -> Int -> m
power x 1 = x
power x n | n < 1 = error "non-positive exponent in 'power'"
| even n = power (x <> x) (n `quot` 2)
| otherwise = power x (n - 1) <> x
parse :: String -> (Integer, Integer)
parse ('c':'u':'t':' ':s) = (1, negate (read s))
parse ('d':_:_:_:_:'w':s) = (read (drop 14 s), 0)
parse ('d':_:_:_:_:'i':_) = (-1, -1)
parse _ = undefined
main :: IO ()
main = do
techlist <- map parse <$> getInput 22
let technique1 = foldl1 (<>) [Affine a b 10007 | (a, b) <- reverse techlist]
technique2 = foldl1 (<>) [Affine a b 119315717514047 | (a, b) <- reverse techlist]
print (apply technique1 2019)
print (apply (power (inverse technique2) 101741582076661) 2020)
|
