結果
問題 | No.3030 ミラー・ラビン素数判定法のテスト |
ユーザー | かりあげクン |
提出日時 | 2020-09-12 11:05:44 |
言語 | Haskell (9.8.2) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,819 bytes |
コンパイル時間 | 1,319 ms |
コンパイル使用メモリ | 204,156 KB |
実行使用メモリ | 13,068 KB |
最終ジャッジ日時 | 2023-08-11 23:06:52 |
合計ジャッジ時間 | 2,644 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | WA | - |
testcase_01 | WA | - |
testcase_02 | WA | - |
testcase_03 | WA | - |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | WA | - |
コンパイルメッセージ
Loaded package environment from /home/judge/.ghc/x86_64-linux-9.6.1/environments/default [1 of 2] Compiling Main ( Main.hs, Main.o ) Main.hs:14:25: warning: [GHC-68441] [-Wdeprecations] In the use of ‘powModInteger’ (imported from GHC.Integer.GMP.Internals): Deprecated: "Use integerPowMod# instead" | 14 | powModInt a n mo = fI $ powModInteger (fi a) (fi n) (fi mo) | ^^^^^^^^^^^^^ [2 of 2] Linking a.out
ソースコード
import qualified Control.Arrow as Arrow import Data.Bits (Bits (unsafeShiftL, unsafeShiftR), FiniteBits (countTrailingZeros)) import Data.Bool (bool) import qualified Data.ByteString.Char8 as BSC8 import qualified Data.Vector.Unboxed as VU import GHC.Integer.GMP.Internals (powModInteger) fi :: Int -> Integer fi = fromIntegral fI :: Integer -> Int fI = fromInteger powModInt :: Int -> Int -> Int -> Int powModInt a n mo = fI $ powModInteger (fi a) (fi n) (fi mo) millerRabin :: Int -> Bool millerRabin n | n <= 3 = n == 2 || n == 3 | even n = False | otherwise = mrCheck n mrCheck :: Int -> Bool mrCheck n | n < 2047 = loop [2] | n < 9080191 = loop [31,73] | n < 4759123141 = loop [2,7,61] | n < 1122004669633 = loop [2,13,23,1662803] | n < 2152302898747 = loop [2,3,5,7,11] | n < 341550071728321 = loop [2,3,5,7,11,13,17] | otherwise = loop [2,325,9375,28178,450775,9780504,1795265022] where m = n - 1 s = countTrailingZeros m d = m `unsafeShiftR` s loop [] = True loop (a:as) | (powModInt (a `mod` n) d n /= 1) = all (\r -> (powModInt a ((1 `unsafeShiftL` r) * d) n) /= m) [0..(s - 1)] | otherwise = loop as type Parser a = BSC8.ByteString -> Maybe (a, BSC8.ByteString) parseInt :: Parser Int parseInt = fmap (Arrow.second BSC8.tail) . BSC8.readInt parse1 :: IO Int parse1 = readLn parseN :: Int -> IO (VU.Vector Int) parseN n = VU.replicateM n parse1 main :: IO () main = do n <- parse1 xs <- parseN n VU.mapM_ (BSC8.putStrLn . solve) xs solve :: Int -> BSC8.ByteString solve n = BSC8.pack $ bool (show n ++ " 0") (show n ++ " 1") (millerRabin n)