Hello all
I am trying to solve this problem https://www.spoj.pl/problems/FCTRL4/1 in Haskell and getting TLE. Could some one please tell me why this code gets TLE. I am using the algorithm explained here http://mathproblems123.wordpress.com/2010/04/15/last-non-zero-digit-of-a-factorial/.
import Data.List
import qualified Data.ByteString.Char8 as BS
helpMod::Integer->Integer->Integer->Integer
helpMod a d n= fun a d where
fun a 1 = mod a n
fun a 2 = mod (a^2) n
fun a d = let
p=fun (mod (a^2) n) (div d 2)
q=if odd d then mod (a*p) n else p
in mod q n
readInt :: BS.ByteString -> Integer
readInt x = case BS.readInteger x of
Just ( i , _ ) -> i
Nothing -> error " upseperable ints "
solve ::Integer -> Integer
solve 0 = 1
solve 1 = 1
solve 2 = 2
solve 3 = 6
solve 4 = 4
solve n = mod ( ( helpMod 2 q 10 ) * ( solve q ) *( solve r ) ) 10 where
( q , r ) = quotRem n 5
main = BS.interact $ BS.unlines. map ( BS.pack . show . solve ) . map readInt. BS.lines