結果
| 問題 |
No.16 累乗の加算
|
| コンテスト | |
| ユーザー |
 poapoa
|
| 提出日時 | 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
ソースコード
{-# LANGUAGE DeriveFunctor #-}
{-# LANGUAGE BangPatterns, BinaryLiterals, CPP, DerivingStrategies #-}
{-# LANGUAGE DerivingVia, FlexibleContexts, FlexibleInstances #-}
{-# LANGUAGE GeneralizedNewtypeDeriving, KindSignatures, LambdaCase #-}
{-# LANGUAGE MagicHash, MultiParamTypeClasses, MultiWayIf #-}
{-# LANGUAGE NumericUnderscores, OverloadedStrings, PatternSynonyms #-}
{-# LANGUAGE RankNTypes, RecordWildCards, ScopedTypeVariables #-}
{-# LANGUAGE StandaloneDeriving, TupleSections, TypeApplications #-}
{-# LANGUAGE TypeFamilies, TypeInType, UnboxedTuples, ViewPatterns #-}
{- base -}
import Control.Applicative
import qualified Control.Arrow as Arrow
import Control.Monad
import Control.Monad.ST
import Data.Bits
import Data.Bool
import Data.Complex
import qualified Data.Char as Char
import qualified Data.Foldable as Foldable
import Data.Function
import qualified Data.List as List
import Data.Maybe
import Data.Monoid
import Data.Ratio
import Data.Ord
import Data.Semigroup
import qualified Data.Word as Word
import Foreign hiding (void)
import GHC.Exts
import Unsafe.Coerce
{- array -}
import qualified Data.Array.IO as ArrIO
import qualified Data.Array.MArray as ArrMA
import qualified Data.Array.ST as ArrST
import qualified Data.Array.Storable as ArrStore
import qualified Data.Array.Unboxed as ArrU
{- bytestring -}
import qualified Data.ByteString as BS
import qualified Data.ByteString.Builder as BSB
import qualified Data.ByteString.Builder.Extra as BSBE
import qualified Data.ByteString.Char8 as BSC8
import qualified Data.ByteString.Lazy as BSL
import qualified Data.ByteString.Lazy.Builder as BSLB
import qualified Data.ByteString.Lazy.Char8 as BSLC8
import qualified Data.ByteString.Unsafe as BSU
{- containers -}
import qualified Data.Graph as Graph
import Data.IntMap (IntMap)
import qualified Data.IntMap as IntMap
import Data.IntSet (IntSet)
import qualified Data.IntSet as IntSet
import qualified Data.Sequence as Seq
import qualified Data.Tree as Tree
{- integer-gmp -}
import GHC.Integer.GMP.Internals
{- vector -}
import qualified Data.Vector as V
import qualified Data.Vector.Generic as VG
import qualified Data.Vector.Generic.Mutable as VGM
import qualified Data.Vector.Mutable as VM
import qualified Data.Vector.Primitive as VP
import qualified Data.Vector.Primitive.Mutable as VPM
import qualified Data.Vector.Unboxed as VU
import qualified Data.Vector.Unboxed.Mutable as VUM
-------------------------------------------------------------------------------
-- main
-------------------------------------------------------------------------------
main :: IO ()
main = do
(x, m) <- parse2
a <- parseM m
print $ flip mod 1000003 $ VU.sum $ VU.map (\i -> powModInt x i 1000003) a
powModInt :: Int -> Int -> Int -> Int
powModInt a b c = fromInteger $ powModInteger (fromIntegral a) (fromIntegral b) (fromIntegral c)
-------------------------------------------------------------------------------
-- 素数
-------------------------------------------------------------------------------
{-
primes :: [Int]
素数列の無限リスト
primesToUA :: Int -> [Int]
nまでの素数を列挙する
millerRabin :: Int -> Bool
nが素数かどうか判定する
primeFactors :: Int -> [Int]
nの素因数分解を求める
totient :: Int -> Int
n以下の正整数でnと互いに素な数の個数
divisor :: Int -> [Int]
nの約数を列挙する(未ソート)
nextPrimeInteger :: Integer -> Integer
最強の関数 指定した数より大きい最初の素数を求める 素数を指定した場合も次の素数を返す
-}
sieveUA :: Int -> ArrU.UArray Int Bool
sieveUA top = ArrST.runSTUArray $ do
let m = (top-1) `div` 2
r = floor . sqrt $ fromIntegral top + 1
sieve <- ArrST.newArray (1,m) True
forM_ [1..r `div` 2] $ \i -> do
isPrime <- ArrST.readArray sieve i
when isPrime $ do
forM_ [2*i*(i+1), 2*i*(i+2)+1..m] $ \j -> do
ArrST.writeArray sieve j False
return sieve
primesToUA :: Int -> [Int]
primesToUA top = 2 : [i*2+1 | (i,True) <- ArrU.assocs $ sieveUA top]
millerRabin :: Int -> Bool
millerRabin n
| n <= 1 = False
| n == 2
|| n == 3
|| n == 5
|| n == 7 = True
| even n = False
| otherwise = mrCheck $ fromIntegral n
powerMR :: Integer -> Integer -> Integer -> Integer
powerMR b e m = loop 1 (b `mod` m) e
where
loop res base pxe
| pxe <= 0 = res
| otherwise =
let res' = if pxe `mod` 2 == 1 then (res * base) `mod` m else res
pxe' = shift pxe (-1)
base' = (base * base) `mod` m
in loop res' base' pxe'
factoringPowers :: Integer -> (Integer, Integer)
factoringPowers n = loop (n - 1) 0
where
loop d s
| even d = loop (d `div` 2) (s + 1)
| otherwise = (s, d)
mrCheck :: Integer -> Bool
mrCheck 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)) ]
where
p' = fromIntegral p :: Double
(s, d) = factoringPowers p
loop [] = True
loop (a:as)
| (powerMR a d p) /= 1 && powLoop 0 = False
| otherwise = loop as
where
powLoop r
| r < s = (powerMR a (2 ^ r * d) p) /= (p - 1) && powLoop (r + 1)
| otherwise = True
primeFactors :: Int -> [Int]
primeFactors a = let
(f, f1) = factorPairOf a
f' = if prime f then [f] else primeFactors f
f1' = if prime f1 then [f1] else primeFactors f1
in f' ++ f1'
where
factorPairOf a = let f = head $ factors a
in (f, a `div` f)
factors a = filter (isFactor a) [2..a-1]
isFactor a b = a `mod` b == 0
prime a = null $ factors a
primes :: Integral a => [a]
primes = map fromIntegral $ [2, 3] ++ primes'
where
primes' = [5] ++ f 1 7 primes'
f m s (p : ps) = [n | n <- ns, gcd m n == 1] ++ f (m * p) (p * p) ps
where ns = [x + y | x <- [s, s + 6 .. p * p - 2], y <- [0, 4]]
totient :: Int -> Int
totient n = n `quot` List.product ps * (List.product $ map (subtract 1) ps)
where ps = map head . List.group $ primeFactors n
divisor :: Int -> [Int]
divisor n = List.foldr f [] $ List.takeWhile ((<= n) . (^ 2)) [1 .. n]
where
f x ds
| r == 0, q /= x = x : q : ds
| r == 0 = x : ds
| otherwise = ds
where
(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 :: Parser Int
parseInt = fmap (Arrow.second BSC8.tail) . BSC8.readInt
parseChar :: [Char] -> VU.Vector Char
parseChar = VU.fromList
parse1 :: IO Int
parse1 = readLn
parse2 :: IO (Int, Int)
parse2 = (\vec -> (vec VU.! 0, vec VU.! 1)) . VU.unfoldrN 2 parseInt <$> BSC8.getLine
parse3 :: IO (Int, Int, Int)
parse3 = (\vec -> (vec VU.! 0, vec VU.! 1, vec VU.! 2)) . VU.unfoldrN 3 parseInt <$> BSC8.getLine
parse4 :: IO (Int, Int, Int, Int)
parse4 = (\vec -> (vec VU.! 0, vec VU.! 1, vec VU.! 2, vec VU.! 3)) . VU.unfoldrN 4 parseInt <$> BSC8.getLine
parseM :: Int -> IO (VU.Vector Int)
parseM m = VU.unfoldrN m parseInt <$> BSC8.getLine
parseN :: Int -> IO (VU.Vector Int)
parseN n = VU.replicateM n parse1
parseNM :: Int -> Int -> IO (V.Vector (VU.Vector Int))
parseNM n m = V.replicateM n $ VU.unfoldrN m parseInt <$> BSC8.getLine