結果

問題 No.368 LCM of K-products
コンテスト
ユーザー はむ吉🐹
提出日時 2016-05-03 13:32:41
言語 Haskell
(9.10.1)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,203 bytes
コンパイル時間 313 ms
コンパイル使用メモリ 150,144 KB
最終ジャッジ日時 2024-11-14 19:43:01
合計ジャッジ時間 972 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
Loaded package environment from /home/judge/.ghc/x86_64-linux-9.8.2/environments/default
[1 of 2] Compiling Main             ( Main.hs, Main.o )

Main.hs:4:1: error: [GHC-87110]
    Could not load module ‘Data.Map.Strict’.
    It is a member of the hidden package ‘containers-0.6.8’.
    Use -v to see a list of the files searched for.
  |
4 | import qualified Data.Map.Strict as Map
  | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

ソースコード

diff # 

import Control.Applicative ((<$>))
import Control.Arrow ((&&&))
import Data.List (genericLength, group, sort)
import qualified Data.Map.Strict as Map

type ExpTable a = Map.Map a [a]
type FactorNumTable a = Map.Map a a

mp :: Integral a => a
mp = 10 ^ 9 + 7

modexp :: Integral a => a -> a -> a -> a
modexp b ex m
    | ex == 0   = 1
    | even ex   = flip mod m $ square $ flip mod m $ modexp b (div ex 2) m
    | otherwise = flip mod m $ mod b m * (flip mod m $ modexp b (ex - 1) m)
    where square x = x * x

-- Based on <http://stackoverflow.com/questions/10398698/haskell-counting-how-many-times-each-distinct-element-in-a-list-occurs this page>.
freq :: (Integral a) => [a] -> [(a, [a])]
freq = map (head &&& (:[]) . genericLength) . group . sort

-- Based on <http://qiita.com/little_Haskeller/items/614a3ae20a517c19bb1f this article> .
primes2 :: Integral a => [a]
primes2 = map fromIntegral primes2'
    where
        primes2' = [2, 3, 5] ++ sieve2 5 7 (drop 2 primes2')
        sieve2 m s (p : ps) = [n | n <- ns, gcd m n == 1] ++ sieve2 (m * p) (p * p) ps
            where ns = [x + y | x <- [s, s + 6 .. p * p - 2], y <- [0, 4]]

-- Based on <https://wiki.haskell.org/Testing_primality this page>.
factorize2 :: Integral a => a -> [a]
factorize2 1 = []
factorize2 n = factorize2' n primes2
    where
        factorize2' n ps@(p : pr)
            | p * p > n    = [n]
            | m == 0       = p : factorize2' d ps
            | otherwise    = factorize2' n pr
            where (d, m) = divMod n p

calcExponents :: Integral a => [a] -> ExpTable a
calcExponents = Map.unionsWith (++) . map ce
    where ce = Map.fromAscList . freq . factorize2

factorNumFromExps :: Integral a => Int -> ExpTable a -> FactorNumTable a
factorNumFromExps k = Map.map (sum . take k . reverse . sort)

lcmFromFactorNum :: Integral a => a -> FactorNumTable a -> a
lcmFromFactorNum m = flip mod m . product . map f . Map.toAscList
    where f (p, n) = modexp p n m

solve :: Integral a => Int -> [a] -> a
solve k xs = lcmFromFactorNum mp $ factorNumFromExps k $ calcExponents xs

main :: IO ()
main = do
    [_, k] <- map read . words <$> getLine
    xs <- map read . words <$> getLine
    print $ solve k xs
0