{-

- Solution to Project Euler problem 182

- Copyright (c) Project Nayuki. All rights reserved.

-

- https://www.nayuki.io/page/project-euler-solutions

- https://github.com/nayuki/Project-Euler-solutions

-}

import qualified EulerLib

p = 1009 :: Integer

q = 3643 :: Integer

main = putStrLn (show ans)

numUnconcealedP = countAllUnconcealed p

numUnconcealedQ = countAllUnconcealed q

minUnconcealedP = minimum numUnconcealedP

minUnconcealedQ = minimum numUnconcealedQ

totient = (p - 1) * (q - 1)

ans = let

cond e = (numUnconcealedP !! (fromInteger (mod e (p - 1)))) == minUnconcealedP

&& (numUnconcealedQ !! (fromInteger (mod e (q - 1)))) == minUnconcealedQ

in sum (filter cond [0 .. (totient - 1)])

countAllUnconcealed :: Integer -> [Integer]

countAllUnconcealed prime = let

func e = if (gcd e (prime - 1)) == 1

then (countUnconcealed prime e)

else 10^20 -- Sentinel

in map func [0 .. (prime - 2)]

countUnconcealed :: Integer -> Integer -> Integer

countUnconcealed modulus e = fromIntegral (EulerLib.count (\m -> (powMod m e modulus) == m) [0 .. (modulus - 1)])

powMod :: Integer -> Integer -> Integer -> Integer

powMod _ 0 m = mod 1 m

powMod x y m

| mod y 2 == 0 = temp

| otherwise = mod (temp * x) m

where

temp = powMod (mod (x * x) m) (div y 2) m