We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Functional Programming
  3. Ad Hoc
  4. Common Divisors
  5. Discussions

Common Divisors

  • lemmaandrew
     + 0 comments

    A fast way to solve this is by utilizing a fact of the prime factors of a number, which can be found here:

    N = A^p x B^q x C^r  here A, B , C are prime numbers and p,q,and r were respective powers of that prime numbers.

Total numbers of factors for N = (p + 1)(q + 1)(r + 1)

    So, what you need to solve this problem is to get the prime factors of a number, and get the product of the powers (+1 for each power) of its prime factors.

    SPOILERS (Haskell)

    SPOILERS (Haskell)

    SPOILERS (Haskell)

    Here is my implementation of this

    import qualified Data.Map.Strict as Map


counter = foldr (\x -> Map.insertWith (+) x 1) Map.empty

-- I'm too lazy to actually implement a prime sieve, so doing (2 : [odd numbers]) is good enough for me
-- Though if you want it to be actually efficient, do a real prime sieve
primeFactors = counter . flip go (2 : [3,5..]) where
  go n (x:xs)
    | x * x > n = [n | n >= x]
    | n `mod` x == 0 = x : go (n `div` x) (x:xs)
    | otherwise = go n xs

-- the aforementioned formula of N = (p + 1)(q + 1)(r + 1)(...)
numFactors = product . map (+1) . Map.elems . primeFactors

solveTestCase a b = numFactors $ gcd a b

main = getLine >> do
    cases <- map (map read . words) <$> lines <$> getContents
    mapM_ (\[a,b] -> print $ solveTestCase a b) cases