My Weblog

Blog about programming and math

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
Advertisements

June 5, 2011 - Posted by | Programming | ,

No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: