You are not logged in. Please login at www.codechef.com to post your questions!

×

Euclid's algorithm.

How to solve linear Diophantine equations( These equations have integer coefficients and are of the form: ax + by = c ) using Euclid's algorithm ???

asked 14 Nov '14, 11:20

dextrous's gravatar image

5★dextrous
1582210
accept rate: 0%


If your equations are of type ax+by=c then you must have two equations to be able to solve them.

Say you have two equations as ax+by=c and mx+ny=k, then you can write it in matrix form as,

| a b | | x | = | c |

| m n | | y | | k |

Now reduce this matrix to Echelon form that means, do some row transformation so that m reduces to 0. To reduce m to zero we will find GCD of a and m by Euclid's algorithm.

Say CGD(a,m) = g.

Do R1 = R1 * g/a and then R2 = R2 - R1 * m/g. This will reduce your system to Echelon form. and now it is very easy to find x and y.

Pseudo- code:

solveSystem()
{
    // Input equations and store them in 2*3 array
    // Out of which first two columns store x and y coefficients
    // and last columns store values of c and k.
    int[][] eq = new int[2][3];
    takeInput(eq);

    int g = gcd(eq[0][0],eq[1][0]); //Use Euclid's algorithm to implement gcd function.
    //Change R1.
    for(int j=0; j<3; j++)
        eq[0][j]*=g/eq[0][0];
    //Change R2.
    for(int j=0; j<3; j++)
        eq[1][j]-= eq[0][j]*eq[1][0]/g;
    //Now your eq matrix is in Echelon form.
    output: y = eq[1][2]/eq[1][1];
    output: x = (eq[0][2] - y* eq[0][1])/eq[0][0];
}
link
This answer is marked "community wiki".

answered 14 Nov '14, 13:33

harshaneelhg's gravatar image

0★harshaneelhg
111
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×26

question asked: 14 Nov '14, 11:20

question was seen: 1,384 times

last updated: 14 Nov '14, 13:33