Submission #11693643

---

Source Code Expand

import           Control.Monad
import qualified Data.Array.IO               as IO
import           Data.Bits
import qualified Data.ByteString.Char8       as BS
import           Data.Char
import           Data.Foldable
import           Data.Maybe
import qualified Data.Sequence               as Seq
import qualified Data.Vector.Unboxed         as V
import qualified Data.Vector.Unboxed.Mutable as VM

readInt = fst . fromJust . BS.readInt
getInt = readInt <$> BS.getLine

primeFactorization :: Int -> [(Int, Int)]
primeFactorization x = pfact x 2 0 []
  where
        sr = floor $ sqrt $ fromIntegral x
        pfact n i r fs | i > sr    = if n > sr then (n,1):fs else fs
                       | otherwise =
                           if n `mod` i == 0
                           then pfact (n `div` i) i (r+1) fs
                           else pfact n (i+1) 0 (if r > 0 then (i,r):fs else fs)
main = do
  n <- getInt

  let p = 10^9 + 7 :: Int
      sr = floor $ sqrt $ fromIntegral n

  v <- VM.new (n+1)
  VM.set v (0::Int)

  forM_ [1..n] $ \x ->
    forM_ (primeFactorization x) $ \(i, r) -> do
      t <- VM.read v i
      VM.write v i (t+r)

  VM.write v 0 (1::Int)
  forM_ [1..n] $ \i -> do
    res <- VM.read v 0
    t <- VM.read v i
    VM.write v 0 (res * (t + 1) `mod` p)

  ans <- VM.read v 0
  print ans

Submission Info

Judge Result