Skip to content

Instantly share code, notes, and snippets.

@rayshih
Created May 14, 2016 03:27
Show Gist options
  • Save rayshih/6f37ce00eb0ead6aeacf7911386731b7 to your computer and use it in GitHub Desktop.
Save rayshih/6f37ce00eb0ead6aeacf7911386731b7 to your computer and use it in GitHub Desktop.
import Data.Functor
readInt = read <$> getLine :: IO Int
readIntArray = map read . words <$> getLine :: IO [Int]
m = 10^9 + 7
mm a b = (a * b) `mod` m
extractCD2 :: (Int, [Int]) -> Int -> (Int, [Int])
extractCD2 (acd, bs) a = case result of (cd, _, bs') -> (acd `mm` cd, bs')
where result = foldl extractCD1 (1, a, []) bs
extractCD1 :: (Int, Int, [Int]) -> Int -> (Int, Int, [Int])
extractCD1 (acd, a, bs') b = (acd `mm` cd, a `div` cd, (b `div` cd):bs')
where cd = gcd a b
solve :: [Int] -> [Int] -> Int
solve as bs = fst . foldl extractCD2 (1, bs) $ as
main = do
n <- readInt
as <- readIntArray
m <- readInt
bs <- readIntArray
print $ solve as bs
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment