結果
問題 | No.368 LCM of K-products |
ユーザー | はむ吉🐹 |
提出日時 | 2016-05-15 19:59:51 |
言語 | Haskell (9.8.2) |
結果 |
CE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 2,484 bytes |
コンパイル時間 | 571 ms |
コンパイル使用メモリ | 150,656 KB |
最終ジャッジ日時 | 2024-11-14 19:44:05 |
合計ジャッジ時間 | 1,195 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。(リジャッジ後のコンパイルエラーは公開されます)
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、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:6: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. | 6 | import qualified Data.Map.Strict as Map | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
ソースコード
import Control.Applicative ((<$>)) import Control.Arrow ((&&&)) import qualified Data.ByteString.Char8 as C import Data.List (genericLength, group, sort) import Data.Maybe (fromJust) import qualified Data.Map.Strict as Map type ExpTable a = Map.Map a [a] type FactorNumTable a = Map.Map a a unsafeReadInteger :: C.ByteString -> Integer unsafeReadInteger = fst . fromJust . C.readInteger unsafeReadInt :: C.ByteString -> Int unsafeReadInt = fst . fromJust . C.readInt 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 unsafeReadInt . C.words <$> C.getLine xs <- map unsafeReadInteger . C.words <$> C.getLine print $ solve k xs