#### A

```import Control.Monad
import Text.Printf
import Data.List

f :: Num a => [a] -> a
f xs = sum \$ zipWith (*) xs (tail xs)

g :: [a] -> [a] -> [a] -> ([a], [a])
g ls rs [] = (ls,rs)
g ls rs [x] = (x:ls,rs)
g ls rs (x:y:zs) = g (x:ls) (y:rs) zs

h :: [Integer] -> Double
h xs = (c*).fromIntegral \$ f (x: reverse ls) + f (x: reverse rs) + (head ls) * (head rs)
where (x:xs') = reverse.sort \$ xs
(ls,rs) = g [] [] xs'
c = (/2).sin \$ 2 * pi / (fromIntegral \$ length xs)

-- output and input function
main :: IO ()
main = do [t] <- getList :: IO [Int]
forM_ [1..t] \$ \i -> do
_ <- getLine
xs <- getList :: IO [Integer]
printf "Case #%d: %f\n" i \$ h xs

getList :: Read a => IO [a]
getList = liftM (map read.words) getLine```

#### B

Project Eulerで似たような問題をやったことがあったので、それを思い出しながら。

```import Control.Monad
import Text.Printf
import Data.List
import ONeillPrimes (primes)
import Data.MemoTrie

-- a^n (mod p)
powMod :: (Integral a, Integral b) => a -> b -> a -> a
powMod a n p | n == 0 = 1
| even n = powMod (mod (a*a) p) (div n 2) p
| otherwise = (a * powMod a (n-1) p)`mod` p

factors :: Integer -> [(Integer, Int)]
factors n = map (\xs -> (head xs, length xs)).group \$ f n primes
where f _ [] = []
f m (p:ps) | p*p > m = [m]
| m `mod` p == 0 = p:f(div m p) (p:ps)
| otherwise = f m ps

totient :: Integer -> Integer
totient n = product [(p-1) * p ^ (k-1) | (p, k) <- factors n]

f, memoF :: Integer -> Integer -> Integer -> Integer
f x 0 m = x `mod` m
f x _ 1 = 0
f x _ 2 | odd x  = 1
| even x = 0
f x n m | mod x m == 0 = 0
f x n m | x < s     = f (x^x) (n-1) m
| c == 1    = 0
| otherwise =  (`mod` m) \$ (a ^ s * (powMod a (mod (b-s) m') c))
where a = memoF x (n-1) m
b = memoF x (n-1) m'
c = g x m
m' = totient c
s = h x (m `div` c)
memoF = memo3 f

g, h :: Integer -> Integer -> Integer
g x m = product [p ^ k | (p, k) <- factors m, mod x p /= 0]
h x c = toInteger.succ.length.takeWhile (\y -> y `mod` c /= 0) \$ iterate (*x) x

-- output and input function
main :: IO ()
main = do [t] <- getList :: IO [Int]
forM_ [1..t] \$ \i -> do
(x:n:m:_) <- getList :: IO [Integer]
printf "Case #%d: %d\n" i \$ memoF x n m

getList :: Read a => IO [a]
getList = liftM (map read.words) getLine
```