My Weblog

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 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
```