結果

問題 No.774 tatyamと素数大富豪
ユーザー かりあげクンかりあげクン
提出日時 2020-08-27 02:57:01
言語 Haskell
(9.8.2)
結果
TLE  
実行時間 -
コード長 3,684 bytes
コンパイル時間 9,331 ms
コンパイル使用メモリ 196,632 KB
実行使用メモリ 23,368 KB
最終ジャッジ日時 2024-04-25 04:28:14
合計ジャッジ時間 15,919 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 TLE -
testcase_01 -- -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
権限があれば一括ダウンロードができます
コンパイルメッセージ
Loaded package environment from /home/judge/.ghc/x86_64-linux-9.8.2/environments/default
[1 of 2] Compiling Main             ( Main.hs, Main.o )
[2 of 2] Linking a.out

ソースコード

diff # 

{-# OPTIONS_GHC -O2 #-}
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE Rank2Types #-}
{-# LANGUAGE TupleSections #-}
{-# LANGUAGE MagicHash #-}

import qualified Control.Arrow               as Arrow
import qualified Control.Monad               as Monad
import qualified Data.Bool                   as Bool
import qualified Data.Bits                   as Bits
import qualified Data.List                   as List
import qualified Data.ByteString.Char8       as BSC8
import qualified Data.Foldable               as Foldable
import qualified Data.List                   as List
import qualified Data.Vector                 as V
import qualified Data.Vector.Unboxed         as VU
import qualified Data.Vector.Unboxed.Mutable as VUM
import qualified Data.Word                   as Word
import           Unsafe.Coerce

----------
-- main --
----------
main :: IO ()
main = do
  _ <- parse1
  xs <- concat . words <$> getLine
  print $ solver $ map (read :: String -> Integer) $ List.permutations xs

solver :: [Integer] -> Integer
solver xs = step xs (-1)
  where
    step :: [Integer] -> Integer -> Integer
    step []     ans = ans
    step (y:ys) ans = step ys (max ans temp)
      where
        temp = if millerRabin (fromInteger y) then y else -1

-----------
-- input --
-----------
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
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

------------------
-- Miller Rabin --
------------------
millerRabin :: Int -> Bool
millerRabin n
  |  n <= 1 = False
  |  n == 2
  || n == 3
  || n == 5
  || n == 7 = True
  |  even n = False
  |  otherwise = mrCheck $ fromIntegral n

powMod :: Integer -> Integer -> Integer -> Integer
powMod 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'  = Bits.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 < 1373653             = loop [2,3]
  | p < 9080191             = loop [31,73]
  | p < 25326001            = loop [2,3,5]
  | p < 4759123141          = loop [2,7,61]
  | p < 1122004669633       = loop [2,13,23,1662803]
  | p < 2152302898747       = loop [2,3,5,7,11]
  | p < 3474749660383       = loop [2,3,5,7,11,13]
  | p < 341550071728321     = loop [2,3,5,7,11,13,17]
  | p < 3825123056546413051 = loop [2,3,5,7,11,13,17,19,23]
  | otherwise               = loop [2,325,9375,28178,450775,9780504,1795265022]
  where
    (s, d) = factoringPowers p
    loop [] = True
    loop (a:as)
      | (powMod a d p) /= 1 && powLoop 0 = False
      | otherwise = loop as
      where
        powLoop r
          | r < s     = (powMod a (2 ^ r * d) p) /= (p - 1)  && powLoop (r + 1)
          | otherwise = True
0