-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathhuge-gcd-fp.hs
More file actions
41 lines (37 loc) · 1.36 KB
/
huge-gcd-fp.hs
File metadata and controls
41 lines (37 loc) · 1.36 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
-- Author: btjanaka (Bryon Tjanaka)
-- Problem: (HackerRank) huge-gcd-fp
-- Title: Huge GCD
-- Link: https://www.hackerrank.com/challenges/huge-gcd-fp/problem
-- Idea: Factor all the numbers in each list then find ones in common.
-- Difficulty: easy
-- Tags: math
import Data.List
-- Returns a list of factors of the given number
factors :: Int -> Int -> [Int]
factors x n | x == 1 = []
| x `mod` n == 0 = n : factors (x `div` n) n
| otherwise = factors x (if n == 2 then 3 else n + 2)
-- Factors all numbers in the list and puts them all in a new list.
allFactors :: [Int] -> [Int]
allFactors xs = sort $ do
i <- xs
factors i 2
-- Computes gcd from two lists of _sorted_ factors.
gcdFromFactors :: [Int] -> [Int] -> Int
gcdFromFactors [] _ = 1
gcdFromFactors _ [] = 1
gcdFromFactors (x : xs) (y : ys)
| x == y = (x * gcdFromFactors xs ys) `mod` 1000000007
| x > y = gcdFromFactors (x : xs) ys
| otherwise = gcdFromFactors xs (y : ys)
main :: IO ()
main = do
_ <- readLn :: IO Int -- read but ignore n
aText <- getLine
_ <- readLn :: IO Int -- read but ignore m
bText <- getLine
let a = map (read :: String -> Int) $ words aText
b = map (read :: String -> Int) $ words bText
aFactored = allFactors a
bFactored = allFactors b
print $ gcdFromFactors aFactored bFactored