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.
| //Problem Statement : https://www.spoj.com/problems/GCD2/ | |
| open System | |
| let parseLine() = | |
| let line = System.Console.ReadLine().Split() | |
| line.[0] |> int, line.[1] |> 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() |
adilakhter λ 