JOIN
Get Time
forums  Revision History
Search My Post History  |  My Watches  |  User Settings
Forums TopCoder Cookbook Algorithm Competitions - Rewriting Phase Using Euclid's Algorithm Revision History (7 edits)
Using Euclid's Algorithm
Problem
You need to find the greatest common divisor (GCD) or the lowest common multiple (LCM) of two numbers. The GCD of two numbers a and b is the greatest number that divides evenly into both a and b. For example the GCD of 24 and 60 is 12.


Solution
Both of these problems and many others can be solved with Euclid’s algorithm. We will begin by explaining how to obtain GCD and then show that LCM is a simple extension. To compute the GCD naively we could start from the smallest of the two numbers and work our way downwards until we find a number that divides into both of them:
for (int i=Math.min(a,b); i>=1; i--)
   if (a%i==0 && b%i==0)
      return i;

Although this method is fast enough for most applications, a much faster approach is to use Euclid's algorithm. Euclid's algorithm iterates over the two numbers until a remainder of 0 is found. The algorithm is based on the principle that the GCD of two numbers does not change if the smaller number is subtracted from the larger number. For example, suppose we want to find the GCD of 2336 and 1314. We begin by expressing the larger number (2336) in terms of the smaller number (1314) plus a remainder:
2336 = 1314 x 1 + 1022

We now do the same with 1314 and 1022:
1314 = 1022 x 1 + 292

We continue this process until we reach a remainder of 0:
1022 = 292 x 3 + 146
292 = 146 x 2 + 0

The last non-zero remainder is the GCD. So the GCD of 2336 and 1314 is 146. This algorithm can be easily coded as a recursive function:
//assume that a and b are positive
public long GCD(long a, long b)
{
   if (b==0) return a;
   return GCD(b,a%b);
}

Using this algorithm we can also find the lowest common multiple (LCM) of two numbers. For example the LCM of 6 and 9 is 18 since 18 is the smallest number that divides both 6 and 9. Notice that 18=(6*9)/3. In general we can express LCM(a,b) as (a*b)/GCD(a,b). To prevent potential overflow we perform division before multiplication in the implementation:
public long LCM(long a, long b)
{
   return b/GCD(a,b)*a;
}


Discussion
Euclid’s algorithm can compute the GCD of large numbers efficiently. In 1844 Gabriel Lamé showed that it never requires more iterations than five times the number of digits h (in base 10) of the smaller number. Since the computational expense of each iteration has order h, the overall complexity grows as h^2.

The algorithm has many theoretical and practical applications. It is an important element of the RSA algorithm. It can also be used to solve linear Diophantine equations: equations with integer coefficients of the form ax + by = c. To solve such equations we need a variation of the Euclid's Algorithm, where we record the coefficients floor(a/b) at each step. We can then use these coefficients to find integers c1 and d1 such that |b*c1 - a*d1| = 1. If c does not divide evenly by GCD(a,b) then there are no integer solutions; otherwise there are an infinite number of integer solutions and one of these is x0 = (+/-)c*d1, y0 = (+/-)c*c1. Note that the signs depend on the sign of b*c1 - a*d1, as well as, the signs of a, b and c. Once we have a single solution (x0,y0) then the general solution takes the form x = x0 + b/GCD(a,b)*t, y = y0 - a/GCD(a,b)*t, where t is an arbitrary integer. The following code implements these idea:
// Find solutions to a linear diophantine equation ax+by=c
// where a, b and c are integers
public void solveDiophantine(long a, long b, long c)
{
	System.out.println("Attempting to solve: "+a+"x + "+b+"y = "+c);
 
	//special case
	if (a==0 && b==0 && c==0)
	{
		System.out.println("x and y can take any value");
		return;
	}
 
	long a1=Math.abs(a);
	long b1=Math.abs(b);
	long c1=0, c2=1;
	long d1=1, d2=0;
	
	while(b1>0)
	{
		long mult=a1/b1;
		long temp=c2;
		c2=c2*mult+c1;
		c1=temp;
		temp=d2;
		d2=d2*mult+d1;
		d1=temp;
		temp=b1;
		b1=a1%b1;
		a1=temp;
	}
 
	long gcd=a1;
	if (gcd==0 || Math.abs(c)%gcd!=0)
	{
		System.out.println("There are no integer solutions!");
		return;
	}
 
	long det=c1*d2-c2*d1;
	long signa=a>0 ? 1: -1;
	long signb=b>0 ? 1: -1;
	long x=-d1*c*det*signa/gcd;
	long y=c1*c*det*signb/gcd;
	System.out.println("One solution is x="+x+", y="+y);
	System.out.println("A general solution is x="+x+" + "+b/gcd+"t, y="+y+" - "+a/gcd+"t");
}


For a more detailed description of the above algorithm, see the following:
http://mathworld.wolfram.com/DiophantineEquation.html
http://mathforum.org/library/drmath/view/51595.html
http://www.wikihow.com/Solve-a-Linear-Diophantine-Equation

Now let's try solving CommonMultiples (Div I 250 SRM 346). We are asked to count how many numbers between lower and upper inclusive are multiples of all numbers in the set a. We begin by finding the LCM of all numbers in a. It can be shown that LCM of many numbers can be expressed as the LCM of individual pairs, eg., LCM(a, b, c, d) = LCM(a, LCM(b, LCM(c,d))). We find the LCM of all numbers in the first for loop and store it in lcm. We have to be careful, because lcm can overflow an int. To avoid overflow we modify our GCD and LCM functions to return longs. Now, the count of numbers not greater than upper having the required property is upper/lcm (integer division). Similarly, the count of numbers less than lower having the required property is (lower-1)/lcm. Taking the difference of these two results gives us the final answer:
public class CommonMultiples
{
	public int countCommMult(int[] a, int lower, int upper)
	{
		long lcm=1;
		for (int i=0; i<a.length; i++) lcm=LCM(lcm,a[i]);
 
		return (int)(upper/lcm-(lower-1)/lcm);
	}
 
	public long GCD(long a, long b)
	{
	   if (b==0) return a;
	   return GCD(b,a%b);
	}
 
	public long LCM(long a, long b)
	{
	   return b/GCD(a,b)*a;
	} 
}

Here are some more practice problems to try:

SRM 358 Div I 500 BalanceScale
SRM 427 Div II 500 DesignCalendar

EDIT2: Added a comment to the gcd() that a,b>0. Thanks to syg96
EDIT3: Fixed some bugs in the diophantine code. Should be correct now.
Using Euclid's Algorithm
Problem
You need to find the greatest common divisor (GCD) or the lowest common multiple (LCM) of two numbers. The GCD of two numbers a and b is the greatest number that divides evenly into both a and b. For example the GCD of 24 and 60 is 12.


Solution
Both of these problems and many others can be solved with Euclid’s algorithm. We will begin by explaining how to obtain GCD and then show that LCM is a simple extension. To compute the GCD naively we could start from the smallest of the two numbers and work our way downwards until we find a number that divides into both of them:
for (int i=Math.min(a,b); i>=1; i--)
   if (a%i==0 && b%i==0)
      return i;

Although this method is fast enough for most applications, a much faster approach is to use Euclid's algorithm. Euclid's algorithm iterates over the two numbers until a remainder of 0 is found. The algorithm is based on the principle that the GCD of two numbers does not change if the smaller number is subtracted from the larger number. For example, suppose we want to find the GCD of 2336 and 1314. We begin by expressing the larger number (2336) in terms of the smaller number (1314) plus a remainder:
2336 = 1314 x 1 + 1022

We now do the same with 1314 and 1022:
1314 = 1022 x 1 + 292

We continue this process until we reach a remainder of 0:
1022 = 292 x 3 + 146
292 = 146 x 2 + 0

The last non-zero remainder is the GCD. So the GCD of 2336 and 1314 is 146. This algorithm can be easily coded as a recursive function:
//assume that a and b are positive
public long GCD(long a, long b)
{
   if (b==0) return a;
   return GCD(b,a%b);
}

Using this algorithm we can also find the lowest common multiple (LCM) of two numbers. For example the LCM of 6 and 9 is 18 since 18 is the smallest number that divides both 6 and 9. Notice that 18=(6*9)/3. In general we can express LCM(a,b) as (a*b)/GCD(a,b). To prevent potential overflow we perform division before multiplication in the implementation:
public long LCM(long a, long b)
{
   return b/GCD(a,b)*a;
}


Discussion
Euclid’s algorithm can compute the GCD of large numbers efficiently. In 1844 Gabriel Lamé showed that it never requires more iterations than five times the number of digits h (in base 10) of the smaller number. Since the computational expense of each iteration has order h, the overall complexity grows as h^2.

The algorithm has many theoretical and practical applications. It is an important element of the RSA algorithm. It can also be used to solve linear Diophantine equations: equations with integer coefficients of the form ax + by = c. To solve such equations we need a variation of the Euclid's Algorithm, where we record the coefficients floor(a/b) at each step. We can then use these coefficients to find integers c1 and d1 such that |b*c1 - a*d1| = 1. If c does not divide evenly by GCD(a,b) then there are no integer solutions; otherwise there are an infinite number of integer solutions and one of these is x0 = (+/-)c*d1, y0 = (+/-)c*c1. Note that the signs depend on the sign of b*c1 - a*d1, as well as, the signs of a, b and c. Once we have a single solution (x0,y0) then the general solution takes the form x = x0 + b/GCD(a,b)*t, y = y0 - a/GCD(a,b)*t, where t is an arbitrary integer. The following code implements these idea:
// Find solutions to a linear diophantine equation ax+by=c
// where a, b and c are integers
public void solveDiophantine(long a, long b, long c)
{
	System.out.println("Attempting to solve: "+a+"x + "+b+"y = "+c);
 
	//special case
	if (a==0 && b==0 && c==0)
	{
		System.out.println("There are no integer solutions!");
		return;
	}
 
	long a1=Math.abs(a);
	long b1=Math.abs(b);
	long c1=0, c2=1;
	long d1=1, d2=0;
	
	while(b1>0)
	{
		long mult=a1/b1;
		long temp=c2;
		c2=c2*mult+c1;
		c1=temp;
		temp=d2;
		d2=d2*mult+d1;
		d1=temp;
		temp=b1;
		b1=a1%b1;
		a1=temp;
	}
 
	long gcd=a1;
	if (gcd==0 || Math.abs(c)%gcd!=0)
	{
		System.out.println("There are no integer solutions!");
		return;
	}
 
	long det=c1*d2-c2*d1;
	long signa=a>0 ? 1: -1;
	long signb=b>0 ? 1: -1;
	long x=-d1*c*det*signa/gcd;
	long y=c1*c*det*signb/gcd;
	System.out.println("One solution is x="+x+", y="+y);
	System.out.println("A general solution is x="+x+" + "+b/gcd+"t, y="+y+" - "+a/gcd+"t");
}


For a more detailed description of the above algorithm, see the following:
http://mathworld.wolfram.com/DiophantineEquation.html
http://mathforum.org/library/drmath/view/51595.html
http://www.wikihow.com/Solve-a-Linear-Diophantine-Equation

Now let's try solving CommonMultiples (Div I 250 SRM 346). We are asked to count how many numbers between lower and upper inclusive are multiples of all numbers in the set a. We begin by finding the LCM of all numbers in a. It can be shown that LCM of many numbers can be expressed as the LCM of individual pairs, eg., LCM(a, b, c, d) = LCM(a, LCM(b, LCM(c,d))). We find the LCM of all numbers in the first for loop and store it in lcm. We have to be careful, because lcm can overflow an int. To avoid overflow we modify our GCD and LCM functions to return longs. Now, the count of numbers not greater than upper having the required property is upper/lcm (integer division). Similarly, the count of numbers less than lower having the required property is (lower-1)/lcm. Taking the difference of these two results gives us the final answer:
public class CommonMultiples
{
	public int countCommMult(int[] a, int lower, int upper)
	{
		long lcm=1;
		for (int i=0; i<a.length; i++) lcm=LCM(lcm,a[i]);
 
		return (int)(upper/lcm-(lower-1)/lcm);
	}
 
	public long GCD(long a, long b)
	{
	   if (b==0) return a;
	   return GCD(b,a%b);
	}
 
	public long LCM(long a, long b)
	{
	   return b/GCD(a,b)*a;
	} 
}

Here are some more practice problems to try:

SRM 358 Div I 500 BalanceScale
SRM 427 Div II 500 DesignCalendar

EDIT2: Added a comment to the gcd() that a,b>0. Thanks to syg96
EDIT3: Fixed some bugs in the diophantine code. Should be correct now.
Using Euclid's Algorithm
Problem
You need to find the greatest common divisor (GCD) or the lowest common multiple (LCM) of two numbers. The GCD of two numbers a and b is the greatest number that divides evenly into both a and b. For example the GCD of 24 and 60 is 12.


Solution
Both of these problems and many others can be solved with Euclid’s algorithm. We will begin by explaining how to obtain GCD and then show that LCM is a simple extension. To compute the GCD naively we could start from the smallest of the two numbers and work our way downwards until we find a number that divides into both of them:
for (int i=Math.min(a,b); i>=1; i--)
   if (a%i==0 && b%i==0)
      return i;

Although this method is fast enough for most applications, a much faster approach is to use Euclid's algorithm. Euclid's algorithm iterates over the two numbers until a remainder of 0 is found. The algorithm is based on the principle that the GCD of two numbers does not change if the smaller number is subtracted from the larger number. For example, suppose we want to find the GCD of 2336 and 1314. We begin by expressing the larger number (2336) in terms of the smaller number (1314) plus a remainder:
2336 = 1314 x 1 + 1022

We now do the same with 1314 and 1022:
1314 = 1022 x 1 + 292

We continue this process until we reach a remainder of 0:
1022 = 292 x 3 + 146
292 = 146 x 2 + 0

The last non-zero remainder is the GCD. So the GCD of 2336 and 1314 is 146. This algorithm can be easily coded as a recursive function:
//assume that a and b are positive
public int GCD(int a, int b)
{
   if (b==0) return a;
   return GCD(b,a%b);
}

Using this algorithm we can also find the lowest common multiple (LCM) of two numbers. For example the LCM of 6 and 9 is 18 since 18 is the smallest number that divides both 6 and 9. Notice that 18=(6*9)/3. In general we can express LCM(a,b) as (a*b)/GCD(a,b). To prevent potential overflow we perform division before multiplication in the implementation:
public int LCM(int a, int b)
{
   return b/GCD(a,b)*a;
}


Discussion
Euclid’s algorithm can compute the GCD of large numbers efficiently. In 1844 Gabriel Lamé showed that it never requires more iterations than five times the number of digits h (in base 10) of the smaller number. Since the computational expense of each iteration has order h, the overall complexity grows as h^2.

The algorithm has many theoretical and practical applications. It is an important element of the RSA algorithm. It can also be used to solve linear Diophantine equations: equations with integer coefficients of the form ax + by = c. To solve such equations we need a variation of the Euclid's Algorithm, where we record the coefficients floor(a/b) at each step. We can then use these coefficients to find integers c1 and d1 such that |b*c1 - a*d1| = 1. If c does not divide evenly by GCD(a,b) then there are no integer solutions; otherwise there are an infinite number of integer solutions and one of these is x0 = (+/-)c*d1, y0 = (+/-)c*c1. Note that the signs depend on the sign of b*c1 - a*d1, as well as, the signs of a, b and c. Once we have a single solution (x0,y0) then the general solution takes the form x = x0 + b/GCD(a,b)*t, y = y0 - a/GCD(a,b)*t, where t is an arbitrary integer. The following code implements these idea:
// Find solutions to a linear diophantine equation ax+by=c
// where a, b and c are integers
public void solveDiophantine(int a, int b, int c)
{
	System.out.println("Attempting to solve: "+a+"x + "+b+"y = "+c);
 
	int a1=Math.abs(a);
	int b1=Math.abs(b);
	int c1=0, c2=1;
	int d1=1, d2=0;
	
	// This loop implements the extended version of Euclid's
	// algorithm, which computes the coefficients floor(a/b)
	// and values c1 and d1
	while(b1>0)
	{
		int mult=a1/b1;
		int temp=c2;
		c2=c2*mult+c1;
		c1=temp;
		temp=d2;
		d2=d2*mult+d1;
		d1=temp;
		temp=b1;
		b1=a1%b1;
		a1=temp;
	}
 
	int gcd=a1;  // GCD(a,b)
	if (Math.abs(c)%gcd!=0)
	{
		System.out.println("There are no integer solutions!");
		return;
	}
 
	int det=c1*d2-c2*d1;
	int signa=a>0 ? 1: -1;
	int signb=b>0 ? 1: -1;
	int x=-d1*c*det*signa/gcd;
	int y=c1*c*det*signb/gcd;
	System.out.println("One solution is x0="+x+", y0="+y);
	System.out.println("A general solution is x="+x+" + "+b/gcd+"t, y="+y+" - "+a/gcd+"t");
}


For a more detailed description of the above algorithm, see the following:
http://mathworld.wolfram.com/DiophantineEquation.html
http://mathforum.org/library/drmath/view/51595.html
http://www.wikihow.com/Solve-a-Linear-Diophantine-Equation

Now let's try solving CommonMultiples (Div I 250 SRM 346). We are asked to count how many numbers between lower and upper inclusive are multiples of all numbers in the set a. We begin by finding the LCM of all numbers in a. It can be shown that LCM of many numbers can be expressed as the LCM of individual pairs, eg., LCM(a, b, c, d) = LCM(a, LCM(b, LCM(c,d))). We find the LCM of all numbers in the first for loop and store it in lcm. We have to be careful, because lcm can overflow an int. To avoid overflow we modify our GCD and LCM functions to return longs. Now, the count of numbers not greater than upper having the required property is upper/lcm (integer division). Similarly, the count of numbers less than lower having the required property is (lower-1)/lcm. Taking the difference of these two results gives us the final answer:
public class CommonMultiples
{
	public int countCommMult(int[] a, int lower, int upper)
	{
		long lcm=1;
		for (int i=0; i<a.length; i++) lcm=LCM(lcm,a[i]);
 
		return (int)(upper/lcm-(lower-1)/lcm);
	}
 
	public long GCD(long a, long b)
	{
	   if (b==0) return a;
	   return GCD(b,a%b);
	}
 
	public long LCM(long a, long b)
	{
	   return b/GCD(a,b)*a;
	} 
}

Here are some more practice problems to try:

SRM 358 Div I 500 BalanceScale
SRM 427 Div II 500 DesignCalendar

EDIT: Can someone please check my solveDiophantive() method, because I am worried that I didn't get the signs right.
EDIT2: Added a comment to the gcd() that a,b>0. Thanks to syg96
Using Euclid's Algorithm
Problem
You need to find the greatest common divisor (GCD) or the lowest common multiple (LCM) of two numbers. The GCD of two numbers a and b is the greatest number that divides evenly into both a and b. For example the GCD of 24 and 60 is 12.


Solution
Both of these problems and many others can be solved with Euclid’s algorithm. We will begin by explaining how to obtain GCD and then show that LCM is a simple extension. To compute the GCD naively we could start from the smallest of the two numbers and work our way downwards until we find a number that divides into both of them:
for (int i=Math.min(a,b); i>=1; i--)
   if (a%i==0 && b%i==0)
      return i;

Although this method is fast enough for most applications, a much faster approach is to use Euclid's algorithm. Euclid's algorithm iterates over the two numbers until a remainder of 0 is found. The algorithm is based on the principle that the GCD of two numbers does not change if the smaller number is subtracted from the larger number. For example, suppose we want to find the GCD of 2336 and 1314. We begin by expressing the larger number (2336) in terms of the smaller number (1314) plus a remainder:
2336 = 1314 x 1 + 1022

We now do the same with 1314 and 1022:
1314 = 1022 x 1 + 292

We continue this process until we reach a remainder of 0:
1022 = 292 x 3 + 146
292 = 146 x 2 + 0

The last non-zero remainder is the GCD. So the GCD of 2336 and 1314 is 146. This algorithm can be easily coded as a recursive function:
//assume that a and b cannot both be 0
public int GCD(int a, int b)
{
   if (b==0) return a;
   return GCD(b,a%b);
}

Using this algorithm we can also find the lowest common multiple (LCM) of two numbers. For example the LCM of 6 and 9 is 18 since 18 is the smallest number that divides both 6 and 9. Notice that 18=(6*9)/3. In general we can express LCM(a,b) as (a*b)/GCD(a,b). To prevent potential overflow we perform division before multiplication in the implementation:
public int LCM(int a, int b)
{
   return b/GCD(a,b)*a;
}


Discussion
Euclid’s algorithm can compute the GCD of large numbers efficiently. In 1844 Gabriel Lamé showed that it never requires more iterations than five times the number of digits h (in base 10) of the smaller number. Since the computational expense of each iteration has order h, the overall complexity grows as h^2.

The algorithm has many theoretical and practical applications. It is an important element of the RSA algorithm. It can also be used to solve linear Diophantine equations: equations with integer coefficients of the form ax + by = c. To solve such equations we need a variation of the Euclid's Algorithm, where we record the coefficients floor(a/b) at each step. We can then use these coefficients to find integers c1 and d1 such that |b*c1 - a*d1| = 1. If c does not divide evenly by GCD(a,b) then there are no integer solutions; otherwise there are an infinite number of integer solutions and one of these is x0 = (+/-)c*d1, y0 = (+/-)c*c1. Note that the signs depend on the sign of b*c1 - a*d1, as well as, the signs of a, b and c. Once we have a single solution (x0,y0) then the general solution takes the form x = x0 + b/GCD(a,b)*t, y = y0 - a/GCD(a,b)*t, where t is an arbitrary integer. The following code implements these idea:
// Find solutions to a linear diophantine equation ax+by=c
// where a, b and c are integers
public void solveDiophantine(int a, int b, int c)
{
	System.out.println("Attempting to solve: "+a+"x + "+b+"y = "+c);
 
	int a1=Math.abs(a);
	int b1=Math.abs(b);
	int c1=0, c2=1;
	int d1=1, d2=0;
	
	// This loop implements the extended version of Euclid's
	// algorithm, which computes the coefficients floor(a/b)
	// and values c1 and d1
	while(b1>0)
	{
		int mult=a1/b1;
		int temp=c2;
		c2=c2*mult+c1;
		c1=temp;
		temp=d2;
		d2=d2*mult+d1;
		d1=temp;
		temp=b1;
		b1=a1%b1;
		a1=temp;
	}
 
	int gcd=a1;  // GCD(a,b)
	if (Math.abs(c)%gcd!=0)
	{
		System.out.println("There are no integer solutions!");
		return;
	}
 
	int det=c1*d2-c2*d1;
	int signa=a>0 ? 1: -1;
	int signb=b>0 ? 1: -1;
	int x=-d1*c*det*signa/gcd;
	int y=c1*c*det*signb/gcd;
	System.out.println("One solution is x0="+x+", y0="+y);
	System.out.println("A general solution is x="+x+" + "+b/gcd+"t, y="+y+" - "+a/gcd+"t");
}


For a more detailed description of the above algorithm, see the following:
http://mathworld.wolfram.com/DiophantineEquation.html
http://mathforum.org/library/drmath/view/51595.html
http://www.wikihow.com/Solve-a-Linear-Diophantine-Equation

Now let's try solving CommonMultiples (Div I 250 SRM 346). We are asked to count how many numbers between lower and upper inclusive are multiples of all numbers in the set a. We begin by finding the LCM of all numbers in a. It can be shown that LCM of many numbers can be expressed as the LCM of individual pairs, eg., LCM(a, b, c, d) = LCM(a, LCM(b, LCM(c,d))). We find the LCM of all numbers in the first for loop and store it in lcm. We have to be careful, because lcm can overflow an int. To avoid overflow we modify our GCD and LCM functions to return longs. Now, the count of numbers not greater than upper having the required property is upper/lcm (integer division). Similarly, the count of numbers less than lower having the required property is (lower-1)/lcm. Taking the difference of these two results gives us the final answer:
public class CommonMultiples
{
	public int countCommMult(int[] a, int lower, int upper)
	{
		long lcm=1;
		for (int i=0; i<a.length; i++) lcm=LCM(lcm,a[i]);
 
		return (int)(upper/lcm-(lower-1)/lcm);
	}
 
	public long GCD(long a, long b)
	{
	   if (b==0) return a;
	   return GCD(b,a%b);
	}
 
	public long LCM(long a, long b)
	{
	   return b/GCD(a,b)*a;
	} 
}

Here are some more practice problems to try:

SRM 358 Div I 500 BalanceScale
SRM 427 Div II 500 DesignCalendar

EDIT: Can someone please check my solveDiophantive() method, because I am worried that I didn't get the signs right.
Using Euclid's Algorithm
Problem
You need to find the greatest common divisor (GCD) or the lowest common multiple (LCM) of two numbers. The GCD of two numbers a and b is the greatest number that divides evenly into both a and b. For example the GCD of 24 and 60 is 12.


Solution
Both of these problems and many others can be solved with Euclid’s algorithm. We will begin by explaining how to obtain GCD and then show that LCM is a simple extension. To compute the GCD naively we could start from the smallest of the two numbers and work our way downwards until we find a number that divides into both of them:
for (int i=Math.min(a,b); i>=1; i--)
   if (a%i==0 && b%i==0)
      return i;

Although this method is fast enough for most applications, a much faster approach is to use Euclid's algorithm. Euclid's algorithm iterates over the two numbers until a remainder of 0 is found. The algorithm is based on the principle that the GCD of two numbers does not change if the smaller number is subtracted from the larger number. For example, suppose we want to find the GCD of 2336 and 1314. We begin by expressing the larger number (2336) in terms of the smaller number (1314) plus a remainder:
2336 = 1314 x 1 + 1022

We now do the same with 1314 and 1022:
1314 = 1022 x 1 + 292

We continue this process until we reach a remainder of 0:
1022 = 292 x 3 + 146
292 = 146 x 2 + 0

The last non-zero remainder is the GCD. So the GCD of 2336 and 1314 is 146. This algorithm can be easily coded as a recursive function:
//assume that a and b cannot both be 0
public int GCD(int a, int b)
{
   if (b==0) return a;
   return GCD(b,a%b);
}

Using this algorithm we can also find the lowest common multiple (LCM) of two numbers. For example the LCM of 6 and 9 is 18 since 18 is the smallest number that divides both 6 and 9. Notice that 18=(6*9)/3. In general we can express LCM(a,b) as (a*b)/GCD(a,b). To prevent potential overflow we perform division before multiplication in the implementation:
public int LCM(int a, int b)
{
   return b/GCD(a,b)*a;
}


Discussion
Euclid’s algorithm can compute the GCD of large numbers efficiently. In 1844 Gabriel Lamé showed that it never requires more iterations than five times the number of digits h (in base 10) of the smaller number. Since the computational expense of each iteration has order h, the overall complexity grows as h^2.

The algorithm has many theoretical and practical applications. It is an important element of the RSA algorithm. It can also be used to solve linear Diophantine equations: equations with integer coefficients of the form ax + by = c. To solve such equations we need a variation of the Euclid's Algorithm, where we record the coefficients floor(a/b) at each step. We can then use these coefficients to find integers c1 and d1 such that |b*c1 - a*d1| = 1. If c does not divide evenly by GCD(a,b) then there are no integer solutions; otherwise there are an infinite number of integer solutions and one of these is x0 = (+/-)c*d1, y0 = (+/-)c*c1. Note that the signs depend on the sign of b*c1 - a*d1, as well as, the signs of a, b and c. Once we have a single solution (x0,y0) then the general solution takes the form x = x0 + b/GCD(a,b)*t, y = y0 - a/GCD(a,b)*t, where t is an arbitrary integer. The following code implements these idea:
// Find solutions to a linear diophantine equation ax+by=c
// where a, b and c are integers
public static void solveDiophantine(int a, int b, int c)
{
	System.out.println("Attempting to solve: "+a+"x + "+b+"y = "+c);
 
	int a1=Math.abs(a);
	int b1=Math.abs(b);
	int c1=0, c2=1;
	int d1=1, d2=0;
	
	// This loop implements the extended version of Euclid's
	// algorithm, which computes the coefficients floor(a/b)
	// and values c1 and d1
	while(b1>0)
	{
		int mult=a1/b1;
		int temp=c2;
		c2=c2*mult+c1;
		c1=temp;
		temp=d2;
		d2=d2*mult+d1;
		d1=temp;
		temp=b1;
		b1=a1%b1;
		a1=temp;
	}
 
	int gcd=a1;  // GCD(a,b)
	if (Math.abs(c)%gcd!=0)
	{
		System.out.println("There are no integer solutions!");
		return;
	}
 
	int det=c1*d2-c2*d1;
	int signa=a>0 ? 1: -1;
	int signb=b>0 ? 1: -1;
	int x=-d1*c*det*signa/gcd;
	int y=c1*c*det*signb/gcd;
	System.out.println("One solution is x="+x+", y="+y);
	System.out.println("A general solution is x="+x+" + "+b/gcd+"t, y="+y+" - "+a/gcd+"t");
}


For a more detailed description of the above algorithm, see the following:
http://mathworld.wolfram.com/DiophantineEquation.html
http://mathforum.org/library/drmath/view/51595.html
http://www.wikihow.com/Solve-a-Linear-Diophantine-Equation

Now let's try solving CommonMultiples (Div I 250 SRM 346). We are asked to count how many numbers between lower and upper inclusive are multiples of all numbers in the set a. We begin by finding the LCM of all numbers in a. It can be shown that LCM of many numbers can be expressed as the LCM of individual pairs, eg., LCM(a, b, c, d) = LCM(a, LCM(b, LCM(c,d))). We find the LCM of all numbers in the first for loop and store it in lcm. We have to be careful, because lcm can overflow an int. To avoid overflow we modify our GCD and LCM functions to return longs. Now, the count of numbers not greater than upper having the required property is upper/lcm (integer division). Similarly, the count of numbers less than lower having the required property is (lower-1)/lcm. Taking the difference of these two results gives us the final answer:
public class CommonMultiples
{
	public int countCommMult(int[] a, int lower, int upper)
	{
		long lcm=1;
		for (int i=0; i<a.length; i++) lcm=LCM(lcm,a[i]);
 
		return (int)(upper/lcm-(lower-1)/lcm);
	}
 
	public long GCD(long a, long b)
	{
	   if (b==0) return a;
	   return GCD(b,a%b);
	}
 
	public long LCM(long a, long b)
	{
	   return b/GCD(a,b)*a;
	} 
}

Here are some more practice problems to try:

SRM 358 Div I 500 BalanceScale
SRM 427 Div II 500 DesignCalendar

EDIT: Can someone please check my solveDiophantive() method, because I am worried that I didn't get the signs right.
Using Euclid's Algorithm
Problem
You need to find the greatest common divisor (GCD) or the lowest common multiple (LCM) of two numbers. The GCD of two numbers a and b is the greatest number that divides evenly into both a and b. For example the GCD of 24 and 60 is 12.


Solution
Both of these problems and many others can be solved with Euclid’s algorithm. We will begin by explaining how to obtain GCD and then show that LCM is a simple extension. To compute the GCD naively we could start from the smallest of the two numbers and work our way downwards until we find a number that divides into both of them:
for (int i=Math.min(a,b); i>=1; i--)
   if (a%i==0 && b%i==0)
      return i;

Although this method is fast enough for most applications, a much faster approach is to use Euclid's algorithm. Euclid's algorithm iterates over the two numbers until a remainder of 0 is found. The algorithm is based on the principle that the GCD of two numbers does not change if the smaller number is subtracted from the larger number. For example, suppose we want to find the GCD of 2336 and 1314. We begin by expressing the larger number (2336) in terms of the smaller number (1314) plus a remainder:
2336 = 1314 x 1 + 1022

We now do the same with 1314 and 1022:
1314 = 1022 x 1 + 292

We continue this process until we reach a remainder of 0:
1022 = 292 x 3 + 146
292 = 146 x 2 + 0

The last non-zero remainder is the GCD. So the GCD of 2336 and 1314 is 146. This algorithm can be easily coded as a recursive function:
//assume that a and b cannot both be 0
public int GCD(int a, int b)
{
   if (b==0) return a;
   return GCD(b,a%b);
}

Using this algorithm we can also find the lowest common multiple (LCM) of two numbers. For example the LCM of 6 and 9 is 18 since 18 is the smallest number that divides both 6 and 9. Notice that 18=(6*9)/3. In general we can express LCM(a,b) as (a*b)/GCD(a,b). To prevent potential overflow we perform division before multiplication in the implementation:
public int LCM(int a, int b)
{
   return b/GCD(a,b)*a;
}


Discussion
Euclid’s algorithm can compute the GCD of large numbers efficiently. In 1844 Gabriel Lamé showed that it never requires more iterations than five times the number of digits h (in base 10) of the smaller number. Since the computational expense of each iteration has order h, the overall complexity grows as h^2.

The algorithm has many theoretical and practical applications. It is an important element of the RSA algorithm. It can also be used to solve linear Diophantine equations: equations with integer coefficients of the form ax + by = c.

Now let's try solving CommonMultiples (Div I 250 SRM 346). We are asked to count how many numbers between lower and upper inclusive are multiples of all numbers in the set a. We begin by finding the LCM of all numbers in a. It can be shown that LCM of many numbers can be expressed as the LCM of individual pairs, eg., LCM(a, b, c, d) = LCM(a, LCM(b, LCM(c,d))). We find the LCM of all numbers in the first for loop and store it in lcm. We have to be careful, because lcm can overflow an int. To avoid overflow we modify our GCD and LCM functions to return longs. Now, the count of numbers not greater than upper having the required property is upper/lcm (integer division). Similarly, the count of numbers less than lower having the required property is (lower-1)/lcm. Taking the difference of these two results gives us the final answer:
public class CommonMultiples
{
	public int countCommMult(int[] a, int lower, int upper)
	{
		long lcm=1;
		for (int i=0; i<a.length; i++) lcm=LCM(lcm,a[i]);
 
		return (int)(upper/lcm-(lower-1)/lcm);
	}
 
	public long GCD(long a, long b)
	{
	   if (b==0) return a;
	   return GCD(b,a%b);
	}
 
	public long LCM(long a, long b)
	{
	   return b/GCD(a,b)*a;
	} 
}

Here are some more practice problems to try:

SRM 358 Div I 500 BalanceScale
SRM 427 Div II 500 DesignCalendar
Using Euclid's Algorithm
Problem
You need to find the greatest common divisor (GCD) or the lowest common multiple (LCM) of two numbers. The GCD of two numbers a and b is the greatest number that divides evenly into both a and b. For example the GCD of 24 and 60 is 12.


Solution
Both of these problems and many others can be solved with Euclid’s algorithm. We will begin by explaining how to obtain GCD and then show that LCM is a simple extension. To compute the GCD naively we could start from the smallest of the two numbers and work our way downwards until we find a number that divides into both of them:
for (int i=Math.min(a,b); i>=1; i--)
   if (a%i==0 && b%i==0)
      return i;

Although this method is fast enough for most applications, a much faster approach is to use Euclid's algorithm. Euclid's algorithm iterates over the two numbers until a remainder of 0 is found. The algorithm is based on the principle that the GCD of two numbers does not change if the smaller number is subtracted from the larger number. For example, suppose we want to find the GCD of 2336 and 1314. We begin by expressing the larger number (2336) in terms of the smaller number (1314) plus a remainder:
2336 = 1314 x 1 + 1022

We now do the same with 1314 and 1022:
1314 = 1022 x 1 + 292

We continue this process until we reach a remainder of 0:
1022 = 292 x 3 + 146
292 = 146 x 2 + 0

The last non-zero remainder is the GCD. So the GCD of 2336 and 1314 is 146. This algorithm can be easily coded as a recursive function:
//assume that a and b cannot both be 0
public int GCD(int a, int b)
{
   if (b==0) return a;
   return GCD(b,a%b);
}

Using this algorithm we can also find the lowest common multiple (LCM) of two numbers. For example the LCM of 6 and 9 is 18 since 18 is the smallest number that divides both 6 and 9. Notice that 18=(6*9)/3. In general we can express LCM(a,b) as (a*b)/GCD(a,b). To prevent potential overflow we perform division before multiplication in the implementation:
public int LCM(int a, int b)
{
   return b/GCD(a,b)*a;
}


Discussion
Euclid’s algorithm can compute the GCD of large numbers efficiently. In 1844 Gabriel Lamé showed that it never requires more iterations than five times the number of digits h (in base 10) of the smaller number. Since the computational expense of each iteration has order h, the overall complexity grows as h^2.

The algorithm has many theoretical and practical applications. It is an important element of the RSA algorithm. It can also be used to solve linear Diophantine equations: equations with integer coefficients of the form ax + by = c.

Here are some practice problems to try:

SRM 346 Div I 250 CommonMultiples
SRM 358 Div I 500 BalanceScale
SRM 427 Div II 500 DesignCalendar
Using Euclid's Algorithm
Problem
You need to find the greatest common divisor (GCD) or the lowest common multiple (LCM) of two numbers. The GCD of two numbers a and b is the greatest number that divides evenly into both a and b. For example the GCD of 24 and 60 is 12.


Solution
Both of these problems and many others can be solved with Euclid’s algorithm. We will begin by explaining how to obtain GCD and then show that LCM is a simple extension. To compute the GCD naively we could start from the smallest of the two numbers and work our way downwards until we find a number that divides into both of them:
for (int i=Math.min(a,b); i>=1; i--)
   if (a%i==0 && b%i==0)
      return i;

Although this method is fast enough for most applications, a much faster approach is to use Euclid's algorithm. Euclid's algorithm iterates over the two numbers until a remainder of 0 is found. The algorithm is based on the principle that the GCD of two numbers does not change if the smaller number is subtracted from the larger number. For example, suppose we want to find the GCD of 2336 and 1314. We begin by expressing the larger number (2336) in terms of the smaller number (1314) plus a remainder:
2336 = 1314 x 1 + 1022

We now do the same with 1314 and 1022:
1314 = 1022 x 1 + 292

We continue this process until we reach a remainder of 0:
1022 = 292 x 3 + 146
292 = 146 x 2 + 0

The last non-zero remainder is the GCD. So the GCD of 2336 and 1314 is 146. This algorithm can be easily coded as a recursive function:
//assume that a and b cannot both be 0
public int GCD(int a, int b)
{
   if (b==0) return a;
   return GCD(b,a%b);
}

Using this algorithm we can also find the lowest common multiple (LCM) of two numbers. For example the LCM of 6 and 9 is 18 since 18 is the smallest number that divides both 6 and 9. Notice that 18=(6*9)/3. In general we can express LCM(a,b) as (a*b)/GCD(a,b). To prevent potential overflow we perform division before multiplication in the implementation:
public int LCM(int a, int b)
{
   return b/GCD(a,b)*a;
}


Discussion
Euclid’s algorithm can compute the GCD of large numbers efficiently. In 1844 Gabriel Lamé showed that it never requires more iterations than five times the number of digits h (in base 10) of the smaller number. Since the computational expense of each iteration has order h, the overall complexity grows as h^2.

The algorithm has many theoretical and practical applications. It is an important element of the RSA algorithm. It can also be used to solve linear Diophantine equations: equations with integer coefficients of the form ax + by = c.