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

No comments yet.

## Leave a Reply