結果
問題 | No.16 累乗の加算 |
ユーザー |
![]() |
提出日時 | 2020-08-31 15:38:59 |
言語 | Haskell (9.10.1) |
結果 |
CE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 8,927 bytes |
コンパイル時間 | 4,898 ms |
コンパイル使用メモリ | 170,240 KB |
最終ジャッジ日時 | 2024-11-14 23:48:01 |
合計ジャッジ時間 | 5,632 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。(リジャッジ後のコンパイルエラーは公開されます)
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
Loaded package environment from /home/judge/.ghc/x86_64-linux-9.8.2/environments/default Main.hs:9:28: warning: [GHC-53692] [-Wdeprecated-flags] -XTypeInType is deprecated: use -XDataKinds and -XPolyKinds instead | 9 | {-# LANGUAGE TypeFamilies, TypeInType, UnboxedTuples, ViewPatterns #-} | ^^^^^^^^^^ [1 of 2] Compiling Main ( Main.hs, Main.o ) Main.hs:44:1: error: [GHC-61948] Could not find module ‘Data.ByteString.Lazy.Builder’. Perhaps you meant Data.ByteString.Builder (from bytestring-0.12.1.0) Data.ByteString.Lazy.Char8 (from bytestring-0.12.1.0) Data.ByteString.Lazy.ReadInt Use -v to see a list of the files searched for. | 44 | import qualified Data.ByteString.Lazy.Builder as BSLB | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Main.hs:48:1: error: [GHC-87110] Could not load module ‘Data.Graph’. It is a member of the hidden package ‘containers-0.6.8’. Use -v to see a list of the files searched for. | 48 | import qualified Data.Graph as Graph | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Main.hs:49:1: error: [GHC-87110] Could not load module ‘Data.IntMap’. It is a member of the hidden package ‘containers-0.6.8’. Use -v to see a list of the files searched for. | 49 | import Data.IntMap (IntMap) | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Main.hs:50:1: error: [GHC-87110] Could not load module ‘Data.IntMap’. It is a member of the hidden package ‘containers-0.6.8’. Use -v to see a list of the files searched for. | 50 | import qualified Data.IntMap as IntMap | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Main.hs:51:1: error: [GHC-87110] Could not load module ‘Data.IntSet’. It is a member of the hidden package ‘containers-0.6.8’. Use -v to see a list of the files searc
ソースコード
LANGUAGELANGUAGELANGUAGELANGUAGELANGUAGELANGUAGELANGUAGELANGUAGELANGUAGE{- base -}importControl.ApplicativeimportqualifiedControl.ArrowasArrowimportControl.MonadimportControl.Monad.STimportData.BitsimportData.BoolimportData.CompleximportqualifiedData.CharasCharimportqualifiedData.FoldableasFoldableimportData.FunctionimportqualifiedData.ListasListimportData.MaybeimportData.MonoidimportData.RatioimportData.OrdimportData.SemigroupimportqualifiedData.WordasWordimportForeignhidingvoidimportGHC.ExtsimportUnsafe.Coerce{- array -}importqualifiedData.Array.IOasArrIOimportqualifiedData.Array.MArrayasArrMAimportqualifiedData.Array.STasArrSTimportqualifiedData.Array.StorableasArrStoreimportqualifiedData.Array.UnboxedasArrU{- bytestring -}importqualifiedData.ByteStringasBSimportqualifiedData.ByteString.BuilderasBSBimportqualifiedData.ByteString.Builder.ExtraasBSBEimportqualifiedData.ByteString.CharasBSCimportqualifiedData.ByteString.LazyasBSLimportqualifiedData.ByteString.Lazy.BuilderasBSLBimportqualifiedData.ByteString.Lazy.CharasBSLCimportqualifiedData.ByteString.UnsafeasBSU{- containers -}importqualifiedData.GraphasGraphimportData.IntMapIntMapimportqualifiedData.IntMapasIntMapimportData.IntSetIntSetimportqualifiedData.IntSetasIntSetimportqualifiedData.SequenceasSeqimportqualifiedData.TreeasTree{- integer-gmp -}importGHC.Integer.GMP.Internals{- vector -}importqualifiedData.VectorasVimportqualifiedData.Vector.GenericasVGimportqualifiedData.Vector.Generic.MutableasVGMimportqualifiedData.Vector.MutableasVMimportqualifiedData.Vector.PrimitiveasVPimportqualifiedData.Vector.Primitive.MutableasVPMimportqualifiedData.Vector.UnboxedasVUimportqualifiedData.Vector.Unboxed.MutableasVUM--------------------------------------------------------------------------------- main-------------------------------------------------------------------------------main::IO()main = do(x, m) <- parse2a <- parseM mprint $ flip mod 1000003 $ VU.sum $ VU.map (\i -> powModInt x i 1000003) apowModInt::Int->Int->Int->IntpowModInt a b c = fromInteger $ powModInteger (fromIntegral a) (fromIntegral b) (fromIntegral c)--------------------------------------------------------------------------------- 素数-------------------------------------------------------------------------------{-primes :: [Int]素数列の無限リストprimesToUA :: Int -> [Int]nまでの素数を列挙するmillerRabin :: Int -> Boolnが素数かどうか判定するprimeFactors :: Int -> [Int]nの素因数分解を求めるtotient :: Int -> Intn以下の正整数でnと互いに素な数の個数divisor :: Int -> [Int]nの約数を列挙する(未ソート)nextPrimeInteger :: Integer -> Integer最強の関数 指定した数より大きい最初の素数を求める 素数を指定した場合も次の素数を返す-}sieveUA::Int->ArrUUArrayIntBoolsieveUA top = ArrST.runSTUArray $ dolet m = (top-1) `div` 2r = floor . sqrt $ fromIntegral top + 1sieve <- ArrST.newArray (1,m) TrueforM_ [1..r `div` 2] $ \i -> doisPrime <- ArrST.readArray sieve iwhen isPrime $ doforM_ [2*i*(i+1), 2*i*(i+2)+1..m] $ \j -> doArrST.writeArray sieve j Falsereturn sieveprimesToUA::Int->IntprimesToUA top = 2 : [i*2+1 | (i,True) <- ArrU.assocs $ sieveUA top]millerRabin::Int->BoolmillerRabin n| n <= 1 = False| n == 2|| n == 3|| n == 5|| n == 7 = True| even n = False| otherwise = mrCheck $ fromIntegral npowerMR::Integer->Integer->Integer->IntegerpowerMR b e m = loop 1 (b `mod` m) ewhereloop res base pxe| pxe <= 0 = res| otherwise =let res' = if pxe `mod` 2 == 1 then (res * base) `mod` m else respxe' = shift pxe (-1)base' = (base * base) `mod` min loop res' base' pxe'factoringPowers::Integer->IntegerIntegerfactoringPowers n = loop (n - 1) 0whereloop d s| even d = loop (d `div` 2) (s + 1)| otherwise = (s, d)mrCheck::Integer->BoolmrCheck p| p < 2047 = loop [2]| p < 9080191 = loop [31,73]| p < 4759123141 = loop [2,7,61]| p < 1122004669633 = loop [2,13,23,1662803]| p < 2152302898747 = loop [2,3,5,7,11]| p < 341550071728321 = loop [2,3,5,7,11,13,17]| p < 3825123056546413051 = loop [2,3,5,7,11,13,17,19,23]| p < 9223372036854775808 = loop [2,325,9375,28178,450775,9780504,1795265022]| otherwise = loop [ 2 .. min (p - 1) (floor $ 2 * (log p')^(2 :: Int)) ]wherep' = fromIntegral p :: Double(s, d) = factoringPowers ploop [] = Trueloop (a:as)| (powerMR a d p) /= 1 && powLoop 0 = False| otherwise = loop aswherepowLoop r| r < s = (powerMR a (2 ^ r * d) p) /= (p - 1) && powLoop (r + 1)| otherwise = TrueprimeFactors::Int->IntprimeFactors a = let(f, f1) = factorPairOf af' = if prime f then [f] else primeFactors ff1' = if prime f1 then [f1] else primeFactors f1in f' ++ f1'wherefactorPairOf a = let f = head $ factors ain (f, a `div` f)factors a = filter (isFactor a) [2..a-1]isFactor a b = a `mod` b == 0prime a = null $ factors aprimes::Integrala=>aprimes = map fromIntegral $ [2, 3] ++ primes'whereprimes' = [5] ++ f 1 7 primes'f m s (p : ps) = [n | n <- ns, gcd m n == 1] ++ f (m * p) (p * p) pswhere ns = [x + y | x <- [s, s + 6 .. p * p - 2], y <- [0, 4]]totient::Int->Inttotient n = n `quot` List.product ps * (List.product $ map (subtract 1) ps)where ps = map head . List.group $ primeFactors ndivisor::Int->Intdivisor n = List.foldr f [] $ List.takeWhile ((<= n) . (^ 2)) [1 .. n]wheref x ds| r == 0, q /= x = x : q : ds| r == 0 = x : ds| otherwise = dswhere(q, r) = n `divMod` x--------------------------------------------------------------------------------- 入力-------------------------------------------------------------------------------{-parse1 2 3 4横に1,2,3,4個の空白区切りの数字をIntで読み取るparseM m横にm個の空白区切りの数字をVU.Vector Intで読み取るparseN n縦にn個の行区切りの数字をVU.Vector Intで読み取るparseNM n m横にm個、縦にn個の数字をV.Vector (VU.Vector Int)で読み取るparseCha文字列を一文字ずつVU.Vector Charで読み取る-}type Parser a = BSC8.ByteString -> Maybe (a, BSC8.ByteString)parseInt::ParserIntparseInt = fmap (Arrow.second BSC8.tail) . BSC8.readIntparseChar::Char->VUVectorCharparseChar = VU.fromListparse1::IOIntparse1 = readLnparse2::IOIntIntparse2 = (\vec -> (vec VU.! 0, vec VU.! 1)) . VU.unfoldrN 2 parseInt <$> BSC8.getLineparse3::IOIntIntIntparse3 = (\vec -> (vec VU.! 0, vec VU.! 1, vec VU.! 2)) . VU.unfoldrN 3 parseInt <$> BSC8.getLineparse4::IOIntIntIntIntparse4 = (\vec -> (vec VU.! 0, vec VU.! 1, vec VU.! 2, vec VU.! 3)) . VU.unfoldrN 4 parseInt <$> BSC8.getLineparseM::Int->IOVUVectorIntparseM m = VU.unfoldrN m parseInt <$> BSC8.getLineparseN::Int->IOVUVectorIntparseN n = VU.replicateM n parse1parseNM::Int->Int->IOVVectorVUVectorIntparseNM n m = V.replicateM n $ VU.unfoldrN m parseInt <$> BSC8.getLine