My Weblog

Blog about programming and math

SPOJ 9161. Legendre symbol

SPOJ 9161. Legendre symbol is related to Jacobian symbol.The Jacobi symbol is a generalization of the Legendre symbol. I just submitted my code from Solovay–Strassen primality test and accepted.Accepted Haskell code

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

readInt :: BS.ByteString -> Integer
readInt = fst . fromJust . BS.readInteger


jacobi::Integral a => a -> a -> a
jacobi a n
 	| a == 0 = if n == 1 then 1 else 0
	| a == 2 && ( mod n 8 == 1 || mod n 8 == 7 ) = 1
	| a == 2 && ( mod n 8 == 3 || mod n 8 == 5 ) = -1
	| a >= n = jacobi ( mod a n ) n
	| even a = jacobi 2 n * jacobi ( div a 2 ) n
	| mod a 4 == 3 && mod n 4 == 3 = -jacobi n a
	| otherwise = jacobi n a


legend :: [Integer]  -> BS.ByteString
legend (a:p:_) = BS.pack.show $  b where 
		b = jacobi a p 

main = BS.interact $ BS.unlines . map ( legend . map readInt . BS.words ) . tail . BS.lines


Advertisements

July 12, 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: