結果
問題 | No.106 素数が嫌い!2 |
ユーザー | かりあげクン |
提出日時 | 2020-09-11 23:07:09 |
言語 | Haskell (9.6.2) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,596 bytes |
コンパイル時間 | 7,809 ms |
コンパイル使用メモリ | 223,580 KB |
実行使用メモリ | 16,668 KB |
最終ジャッジ日時 | 2023-08-27 16:35:01 |
合計ジャッジ時間 | 22,370 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge14 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 4,492 ms
16,668 KB |
testcase_01 | AC | 3 ms
8,092 KB |
testcase_02 | AC | 3 ms
8,068 KB |
testcase_03 | AC | 3 ms
8,160 KB |
testcase_04 | WA | - |
testcase_05 | TLE | - |
testcase_06 | -- | - |
testcase_07 | -- | - |
testcase_08 | -- | - |
testcase_09 | -- | - |
testcase_10 | -- | - |
testcase_11 | -- | - |
testcase_12 | -- | - |
testcase_13 | -- | - |
testcase_14 | -- | - |
testcase_15 | -- | - |
コンパイルメッセージ
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:80:25: warning: [GHC-68441] [-Wdeprecations] In the use of ‘powModInteger’ (imported from GHC.Integer.GMP.Internals): Deprecated: "Use integerPowMod# instead" | 80 | powModInt a n mo = fI $ powModInteger (fi a) (fi n) (fi mo) | ^^^^^^^^^^^^^ [2 of 2] Linking a.out
ソースコード
{-# LANGUAGE BangPatterns #-} import Data.Bits import GHC.Integer.GMP.Internals import Control.Monad import Data.List import qualified Control.Arrow as Arrow import qualified Data.ByteString.Char8 as BSC8 import qualified Data.Char as Char import qualified Data.Vector.Unboxed as VU import qualified Data.Set as Set ordNub :: Ord a => [a] -> [a] ordNub xs = foldr (\x k s -> if Set.member x s then k s else x : k (Set.insert x s)) (const []) xs Set.empty fpf :: Int -> [Int] fpf n | n <= 1 = [] | p == n = [p] | otherwise = p : r where p = pollardRho n r = fpf (n `div` p) pollardRho :: Int -> Int pollardRho n | millerRabin n = n | even n = 2 | otherwise = loop 1 (n + 1) where loop c x | c == 0 = x | x < n = x | otherwise = loop (c +%% 1) (innerLoop 2 2 x) where innerLoop xx yy dd | dd' /= 1 = dd' | otherwise = innerLoop xx' yy'' dd' where xx' = xx *%% xx + c yy' = yy *%% yy + c yy'' = yy' *%% yy' + c dd' = gcd (xx' -%% yy'') n (+%%) :: Int -> Int -> Int (+%%) x y | x + y >= n = x + y - n | otherwise = x + y (-%%) :: Int -> Int -> Int (-%%) x y | x - y < 0 = x - y + n | otherwise = x - y (*%%) :: Int -> Int -> Int (*%%) x y = x * y `rem` n (/%%) :: Int -> Int -> Int (/%%) x y = go y n 1 0 where go a b u v | b > 0 = case a `quot` b of q -> go b (a - (q * b)) v (u - (q * v)) | otherwise = (x * (u + n)) `rem` n (^%%) :: Int -> Int -> Int (^%%) x m | m > 0 = go 1 x m | m == 0 = 1 | otherwise = go 1 ((/%%) 1 x) (-m) where go !acc !y !l | l .&. 1 == 0 = go acc (y *%% y) (unsafeShiftR l 1) | l == 1 = acc *%% y | otherwise = go (acc *%% y) (y *%% y) (unsafeShiftR (l - 1) 1) ------------------------------------------------------------------------------- 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 <= 1 = False | n == 2 || n == 3 || n == 5 || n == 7 = True | 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 < 2152302898747 = loop [2,3,5,7,11] | 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 d n /= 1) && powLoop 0 = False | otherwise = loop as where powLoop r | r < s = (powModInt a ((1 `unsafeShiftL` r) * d) n) /= m && powLoop (r + 1) | otherwise = True ------------------------------------------------------------------------------- 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 parse2 :: IO (Int, Int) parse2 = (\vec -> (vec VU.! 0, vec VU.! 1)) . VU.unfoldrN 2 parseInt <$> BSC8.getLine main :: IO () main = do (n, k) <- parse2 print $ VU.length $ VU.filter (>= k) $ VU.generate (n + 1) (\i -> length $ ordNub $ sort $ fpf i)