# My Weblog

## SPOJ 1434. Equation [ KPEQU ]

SPOJ 1434. Equation looked hard to me because of factorial in N . I was aware of how to solve $\frac {1} {x} + \frac {1} {y} = \frac {1} {N}$ but factorial in this problem gave me lot of pain.Given equation can be written as ( N! – x) * ( N! – y) = ${(N!)} ^2$. Now the number of solutions for any number N will be $(2{a_1}+1) *(2{a_2}+1) ....(2{a_k} + 1)$ where N! = $2^{a_1} * 3^{a_2}*5^{a_3} .....{p_k}^{a_k}$. I was not sure how to count number of primes in factorial and suddenly realised it [ $\frac n p + \frac n {p^2} + \frac n {p^3}$….] . 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