My Weblog

Blog about programming and math

SPOJ 4421. Irreducible polynomials over GF2

SPOJ 4421. Irreducible polynomials over GF2 is too easy in Haskell . For algorithm , mathworld explains it very well. My only concern was calculation of mobius function but under given time limit , mobius can be calculated using prime factorisation. Today i learn nice use of sequence from here.Before this , i used sequence only with IO monads. Accepted Haskell code

import Data.List
import Control.Monad
import Data.Maybe
import qualified Data.ByteString.Char8 as BS

prime :: [Integer]
prime = 2:3:filter isPrime [2*k+1 | k<-[2..]]

isPrime :: Integer -> Bool
isPrime n = all ((/=0). mod n  ).takeWhile ( <= ( truncate.sqrt.fromIntegral $ n) ) $ prime

pfactor :: Integer -> [ Integer ] -> [Integer]
pfactor n p@( x : xs ) 
   | n <= 1 = [] 
   | x ^ 2  > n = [ n ]
   | mod n x == 0 = x : pfactor ( div n x ) p 
   | otherwise = pfactor n xs 

mobius :: Integer -> Integer 
mobius 1 = 1 
mobius n 
    | facs == ( nub facs ) = ( -1 ) ^ len
    | otherwise = 0
	where 
	 facs = pfactor n prime 
	 len = genericLength facs 

--nice use of monads . https://github.com/bjin/fancy-walks/blob/master/spoj.pl/GF2.hs
divisor :: Integer -> Integer -> [Integer]
divisor n  p = sort $ map product $ sequence mul
  where
    fs = group $ pfactor n prime
    mul = map (scanl (*) 1) fs 

{--
divisor :: Integer -> Integer -> [ Integer ]
divisor n p 
  | n <= 1 = [1]
  | p * p > n = []
  | mod n p == 0 = p : ( div n p ) : divisor n (  p  + 1 ) 
  | otherwise = divisor n  ( p + 1 ) 
--}

solve :: Integer  -> String 
solve  n = show $ div ans n  where 
	ans = sum .  map ( \t -> mobius ( div n t ) * 2 ^ t ) . sort . nub . divisor  n $ 1


main = interact $ unlines . map ( solve . read ) . lines 
Advertisements

August 6, 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: