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

×

# Euclid's algorithm.

 0 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 5★dextrous 158●2●2●10 accept rate: 0%

 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; takeInput(eq); int g = gcd(eq,eq); //Use Euclid's algorithm to implement gcd function. //Change R1. for(int j=0; j<3; j++) eq[j]*=g/eq; //Change R2. for(int j=0; j<3; j++) eq[j]-= eq[j]*eq/g; //Now your eq matrix is in Echelon form. output: y = eq/eq; output: x = (eq - y* eq)/eq; }  link This answer is marked "community wiki". answered 14 Nov '14, 13:33 11●1 accept rate: 0%
 toggle preview community wiki:
Preview

### Follow this question

By Email:

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

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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