結果

問題 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

ソースコード

diff #

{-# 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)
0