Created
May 14, 2016 03:27
-
-
Save rayshih/6f37ce00eb0ead6aeacf7911386731b7 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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