SPOJ 2906. GCD2 with F#

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;
		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.


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 ).


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.


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)=
|> 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
| _ -> ()
view raw gcd2.fs hosted with ❤ by GitHub

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: