# Problem Definition

Frank explained its friend Felman the algorithm of Euclides to calculate the GCD of two numbers. Then Felman implements it algorithm

```int gcd(int a, int b)
{
if (b==0)
return a;
else
return gcd(b,a%b);
}```

and it proposes to Frank that makes it but with a little integer and another integer that has up to 250 digits.

Your task is to help Frank programming an efficient code for the challenge of Felman.

## Input

The first line of the input file contains a number representing the number of lines to follow. Each line consists of two number A and B ( and ).

## Output

Print for each pair (A,B) in the input one integer representing the GCD of A and B.

More on this problem is available here.

# Solution

Greatest common divisor is the largest number that divides both number without any reminder.  Thus, GCD is also called Highest Common Divisor (HCF), or  Greatest Common Factor  (GCF).

The main trick used in the solution lies in the `mod'` function, which effectively reduces the range of the numbers to , that is: where is the outcome of `mod'` function .

Afterwards, a normal `gcd` function can simply be applied on to compute the result.

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
 //Problem Statement : https://www.spoj.com/problems/GCD2/ open System let parseLine() = let line = System.Console.ReadLine().Split() line. |> int, line. |> string let rec gcd a b = match b with | 0 -> a | _ -> gcd b (a%b) // computes b%a let mod' (b:string) (a:int)= b.ToCharArray() |> Array.fold (fun acc x -> ((acc*10 + (((int)x)-48))%a)) 0 let rec solveLines currentLine maxLines = if currentLine < maxLines then let num1,num2 = parseLine() match num1,num2 with | 0,_ -> printfn "%s" num2 | _ -> mod' num2 num1 |> gcd num1 |> printfn "%d" solveLines (currentLine+1) maxLines let solveSpoj2906() = match Console.ReadLine() |> Int32.TryParse with | (true, i) when i > 0 -> solveLines 0 i | _ -> () solveSpoj2906()
view raw gcd2.fs hosted with ❤ by GitHub