結果

問題 No.106 素数が嫌い！2
ユーザー かりあげクンかりあげクン
提出日時 2020-09-11 23:00:08
言語 Haskell
(9.8.2)
結果
TLE  
実行時間 -
コード長 3,466 bytes
コンパイル時間 7,596 ms
コンパイル使用メモリ 212,452 KB
実行使用メモリ 11,892 KB
最終ジャッジ日時 2023-08-27 16:26:57
合計ジャッジ時間 27,814 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 TLE -
testcase_01 AC 3 ms
7,704 KB
testcase_02 AC 2 ms
7,768 KB
testcase_03 AC 3 ms
7,704 KB
testcase_04 TLE -
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:74:25: warning: [GHC-68441] [-Wdeprecations]
    In the use of ‘powModInteger’
    (imported from GHC.Integer.GMP.Internals):
    Deprecated: "Use integerPowMod# instead"
   |
74 | 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

fpf :: Int -> [Int]
fpf n
  | n <= 1 = []
  | p == n = [p]
  | otherwise = l ++ (reverse r)
  where
    p = pollardRho n
    l = fpf p
    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 $ nub $ sort $ fpf i)
0