An efficient way to find all the factors for a number is to first find factors less than or equal to the root of the number.

For example for 26 the root is 5.099. Using the above method we have to test just 5 numbers instead of 25. Only 100 tests in case of 10000.

The factors greater than the root can be found by dividing the number by the factors less than or equal to the number.

Finding the intersection of the factors of all numbers is trivial after that.

IMO this is to much work/optimization for an easy problem - neither the most trivial (bruteforce the common divisors) nor the first order optimization (only bruteforce the divisors of the GCD) will run in time

A Haskell IO template I use

countCommonDivisors :: Int -> Int -> Int
countCommonDivisors a b = -- give your solution over here


main = do     
    s <- getContents
    let u = [map read (words s) | s <- (tail . lines) s]
    putStrLn $ unlines $ map show [countCommonDivisors a b | [a, b] <- u]

Unfortunately, I haven't arrived at that simple algebraic formula. Therefore, I solved the problem counting the number of all possible common divisors algorithmically.

Spoiler ahead!

import Data.List ( group )

count' :: [Int] -> [Int]
count' [] = [0]
count' [x] = [x]
count' (x:xs) = [x] ++ count' xs ++ map (x*) (count' xs)

count :: [Int] -> Int
count = sum . count'

-- 1 stands for the trivial divisor (one)
numDivisors m l = 1 + count ns
  where ns = map length $ group $ factorize $ gcd m l

Testcase 2 has the following input: 8 27 76 16 21 11 10 52 68 80 55 80 71 56 16 39 55 The output is: 1 1 1 3 2 1 4 1 which means for 80 55 the expected number of common factors is 2. 80 = 2^4 * 5 while 55 = 5 * 11, the number of common factors is 1, not 2. Can somebody look into this?

Beautiful but not efficien Haskell solution:

getCommonDivisors m n = length [i | i <- [1..(gcd m n)], (mod m i) == 0, (mod n i) == 0]

main = do
    input <- getContents
    let l = lines input
    mapM_ (
        \x -> do
            let mn = words x
            putStrLn $ show (getCommonDivisors (head mn) (last mn))) (tail l)