## SPOJ 1434. Equation [ KPEQU ]

SPOJ 1434. Equation looked hard to me because of factorial in N . I was aware of how to solve but factorial in this problem gave me lot of pain.Given equation can be written as ( N! – x) * ( N! – y) = . Now the number of solutions for any number N will be where N! = . I was not sure how to count number of primes in factorial and suddenly realised it [ ….] . Haskell code for this problem .

import Data.List isprime :: Integer -> Bool isprime n | n<=1 = False | otherwise = all ( (/=0).mod n ) . takeWhile ( \x -> x*x<= n) $ [2..] --count prime p in n! count :: Integer -> Integer -> Integer count 0 _ = 0 count n p = div n p + count ( div n p ) p plist ::[Integer] plist = filter isprime [2..] solve :: Integer -> String solve 1 = show 1 solve n = show a where p = takeWhile ( <=n) plist a = foldl (\acc x -> acc * ( 2 * ( count n x ) + 1 ) ) 1 p main = interact $ unlines . map ( solve . read ) . init . lines

Advertisements

No comments yet.

## Leave a Reply