1.

// Weber: 10109...

import java.io.IOException;
import java.util.Scanner;
import java.util.StringTokenizer;

public class MainX
{
/**
* Represents a RationalNumber with all Funktions.
* @author qriz
*
*/
private static class RationalNumber
{
private final long num;
private final long denom;

public RationalNumber(long num, long denom)
{
this.num = num;
this.denom = denom;
}

public RationalNumber(long num)
{
this(num,1);
}

public RationalNumber(String rationalNumber)
{
if(rationalNumber.contains("/"))
{
this.num = Long.parseLong(rationalNumber.split("/")[0]);
this.denom = Long.parseLong(rationalNumber.split("/")[1]);
}
else
{
this.num = Long.parseLong(rationalNumber);
this.denom = 1;
}
}

public RationalNumber add(RationalNumber other)
{
long d = denom;
RationalNumber a = this.scale(other.denom);
RationalNumber b = other.scale(d);
return new RationalNumber(a.num +b.num, a.denom);
}

public RationalNumber mul(RationalNumber other)
{
return new RationalNumber(this.num*other.num, this.denom*other.denom);
}

public RationalNumber div(RationalNumber other)
{
return new RationalNumber(this.num*other.denom, this.denom*other.num);
}

private long gcd(long num, long denom)
{
//Euklidischer und steinscher Algorithmus
if (denom == 0)
{
return num;
}
else
{
long oldDenom = 0;
while(denom != 0)
{
oldDenom = denom;
long oldnum = denom;
denom = num%denom;
num = oldnum;
}
return oldDenom;
}
}
private boolean checkIfZero(RationalNumber numberToCheck)
{
RationalNumber otherObj = ((RationalNumber)numberToCheck).cancel();

if(otherObj.num == 0 || otherObj.denom == 0)
return true;

return false;
}

public RationalNumber scale(long faktor)
{
return new RationalNumber(num*faktor, denom*faktor);
}

public RationalNumber cancel()
{
long GCD = gcd(num, denom);
if(GCD == 0)
return this;

long newNum = num, newDenom = denom;
newNum /= GCD;
newDenom /= GCD;
if (newDenom < 0)
{
newNum *= -1;
newDenom *= -1;
}

return new RationalNumber(newNum, newDenom);
}

public String toString()
{
if (denom != 1)
{
return num + "/" + denom;
}
else
{
return num + "";
}
}

@Override
public boolean equals(Object obj)
{
if(obj.getClass() == RationalNumber.class)
{
RationalNumber otherObj = ((RationalNumber)obj).cancel();
RationalNumber thisObj = this.cancel();
if(checkIfZero(otherObj) && checkIfZero(this))
return true;

if(otherObj.num == thisObj.num && otherObj.denom == thisObj.denom)
return true;
}

return false;
}
}

/**
* @param args
*/
public static void main(String[] args) throws IOException
{
Scanner scan = new Scanner(System.in);
int counter = 0;
int numberOfUnknowns = 0;
int numberOfEquations = 0;
RationalNumber[][] matrix;
int rang =0;
RationalNumber factor;
boolean start = true;

do{
//Input.
String input = scan.nextLine();
while(input.equals(""))
input = scan.nextLine();

if(input.equals("0"))
{
break;
}
counter = Integer.parseInt(input);

input = scan.nextLine();
numberOfUnknowns = Integer.parseInt(input.split(" ")[0]);
numberOfEquations = Integer.parseInt(input.split(" ")[1]);
matrix = new RationalNumber[numberOfEquations][numberOfUnknowns+1];

//From String to matrix.
for(int i =0; i<matrix.length;i++)
{
input = scan.nextLine();
StringTokenizer st = new StringTokenizer(input);
for(int j =0; j<matrix[0].length; j++)
{
matrix[i][j] = new RationalNumber(st.nextToken());
}
}

//the R-Form.
int j = -1;
for(int i=0;i<matrix.length;i++)
{
if(j!=i-1)
j++;
else
j=i;

if(j>=matrix[0].length)
break;

//Sort Matrix.
if(matrix[i][j].equals(new RationalNumber(0)))
{

RationalNumber[] line = new RationalNumber[matrix[0].length];
//Copy to Line
for(int col = 0; col<matrix[0].length;col++)
{
line[col] = matrix[i][col];
}

boolean found = false;
int secondRow;
int secondCol;
for(secondCol =j;secondCol<matrix[0].length&&!found;secondCol++)
{
for(secondRow = i; secondRow<matrix.length&&!found;secondRow++)
{
if(!matrix[secondRow][secondCol].equals(new RationalNumber(0))&&secondRow!=i)
{
found = true;
for(int col = 0; col<matrix[0].length;col++)
{
matrix[i][col] = matrix[secondRow][col];
matrix[secondRow][col] = line[col];
}
j=secondCol;
break;
}
else if(!matrix[secondRow][secondCol].equals(new RationalNumber(0))&&secondRow==i)
{
j = secondCol;
found = true;
break;
}
}
}
}

if(i>=matrix.length||j>=matrix[0].length)
break;

RationalNumber upperRow = matrix[i][j];
RationalNumber lowerRow = null;

if(upperRow.equals(new RationalNumber(0)))
continue;

// Set first element in line to 1
factor = new RationalNumber(matrix[i][j].denom, matrix[i][j].num);
for (int k = i; k < matrix[0].length; k++)
{
matrix[i][k].mul(factor);
}

for(int row=i+1;row<matrix.length;row++)
{
lowerRow = null;
for(int col=j; col<matrix[0].length; col++)
{
if(lowerRow == null)
{
lowerRow = matrix[row][col];
if(lowerRow.equals(new RationalNumber(0)))
break;
}
RationalNumber upperRowValue = matrix[i][col].mul(lowerRow).cancel();
RationalNumber lowerRowValue = matrix[row][col].mul(upperRow).mul(new RationalNumber(-1)).cancel();
matrix[row][col] = lowerRowValue.add(upperRowValue).cancel();
}
}
}

rang = 0;
boolean noSolution = false;
//Check Matrix for empty Rows.
for(int row = 0; row<matrix.length;row++)
{
int zeroCounter = 0;
for(int col = 0; col<matrix[0].length-1; col++)
{
if(matrix[row][col].equals(new RationalNumber(0)))
{
zeroCounter++;
}
}
if(zeroCounter == numberOfUnknowns)
{
if(!matrix[row][matrix[0].length-1].equals(new RationalNumber(0)))
{
noSolution = true;
}
}
else
{
rang++;
}
}

if (!start) {
System.out.println();
} else {
start = false;
}

System.out.printf("Solution for Matrix System # %d\n", counter);

if(noSolution)
{
System.out.println("No Solution.");
continue;
}
else if(numberOfUnknowns>rang)
{
System.out.printf("Infinitely many solutions containing %d arbitrary constants.\n", (numberOfUnknowns - rang));
continue;
}

//Gauß-Jordan
matrix[numberOfUnknowns-1][numberOfUnknowns]=matrix[numberOfUnknowns-1][numberOfUnknowns].div(matrix[numberOfUnknowns-1][numberOfUnknowns-1]);
matrix[numberOfUnknowns-1][numberOfUnknowns-1] = new RationalNumber(1);

for(int i=numberOfUnknowns-1;i>0;i--)
{
RationalNumber lowerRow = matrix[i][i];
RationalNumber upperRow = null;

for(int row =i-1;row>=0;row--)
{
upperRow = null;
for(int col=0;col<matrix[0].length;col++)
{
if(upperRow == null)
upperRow = matrix[row][i];

RationalNumber upperRowValue = matrix[row][col].mul(lowerRow).cancel();
RationalNumber lowerRowValue = matrix[i][col].mul(upperRow).mul(new RationalNumber(-1)).cancel();
matrix[row][col] = upperRowValue.add(lowerRowValue).cancel();
}
}
}
for(int i=0;i<numberOfUnknowns;i++)
{
matrix[i][matrix[0].length-1] = matrix[i][matrix[0].length-1].div(matrix[i][i]).cancel();
matrix[i][i] = new RationalNumber(1);
}

//Last Output.
for(int row =0;row<matrix[0].length-1;row++)
{
System.out.printf("x[%d] = %s\n", row + 1, matrix[row][matrix[0].length-1].toString());
}

}
while(true);
}
}

2.

import java.io.IOException;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main5
{

/**
* Represents a RationalNumber with all Funktions.
* @author qriz
*
*/
private static class RationalNumber
{
private final long num;
private final long denom;

public RationalNumber(long num, long denom)
{
this.num = num;
this.denom = denom;
}

public RationalNumber(long num)
{
this(num,1);
}

public RationalNumber(String rationalNumber)
{
if(rationalNumber.contains("/"))
{
this.num = Long.parseLong(rationalNumber.split("/")[0]);
this.denom = Long.parseLong(rationalNumber.split("/")[1]);
}
else
{
this.num = Long.parseLong(rationalNumber);
this.denom = 1;
}
}

public RationalNumber add(RationalNumber other)
{
long d = denom;
RationalNumber a = this.scale(other.denom);
RationalNumber b = other.scale(d);
return new RationalNumber(a.num +b.num, a.denom);
}

public RationalNumber mul(RationalNumber other)
{
return new RationalNumber(this.num*other.num, this.denom*other.denom);
}

public RationalNumber div(RationalNumber other)
{
return new RationalNumber(this.num*other.denom, this.denom*other.num);
}

private long gcd(long num, long denom)
{
//Euklidischer und steinscher Algorithmus
if (denom == 0)
{
return num;
}
else
{
long oldDenom = 0;
while(denom != 0)
{
oldDenom = denom;
long oldnum = denom;
denom = num%denom;
num = oldnum;
}
return oldDenom;
}
}
private boolean checkIfZero(RationalNumber numberToCheck)
{
RationalNumber otherObj = ((RationalNumber)numberToCheck).cancel();

if(otherObj.num == 0 || otherObj.denom == 0)
return true;

return false;
}

public RationalNumber scale(long faktor)
{
return new RationalNumber(num*faktor, denom*faktor);
}

public RationalNumber cancel()
{
long GCD = gcd(num, denom);
if(GCD == 0)
return this;

long newNum = num, newDenom = denom;
newNum /= GCD;
newDenom /= GCD;
if (newDenom < 0)
{
newNum *= -1;
newDenom *= -1;
}

return new RationalNumber(newNum, newDenom);
}

public String toString()
{
if (denom != 1)
{
return num + "/" + denom;
}
else
{
return num + "";
}
}

@Override
public boolean equals(Object obj)
{
if(obj.getClass() == RationalNumber.class)
{
RationalNumber otherObj = ((RationalNumber)obj).cancel();
RationalNumber thisObj = this.cancel();
if(checkIfZero(otherObj) && checkIfZero(this))
return true;

if(otherObj.num == thisObj.num && otherObj.denom == thisObj.denom)
return true;
}

return false;
}
}

/**
* @param args
*/
public static void main(String[] args) throws IOException
{
Scanner scan = new Scanner(System.in);
int counter = 0;
int numberOfUnknowns = 0;
int numberOfEquations = 0;
RationalNumber[][] matrix;
int rang =0;
RationalNumber factor;

do{
//Input.
String input = scan.nextLine();
while(input.equals(""))
input = scan.nextLine();

if(input.equals("0"))
{
break;
}
counter = Integer.parseInt(input);

input = scan.nextLine();
while(input.equals(""))
input = scan.nextLine();
StringTokenizer st = new StringTokenizer(input);
numberOfUnknowns = Integer.parseInt(st.nextToken());
numberOfEquations = Integer.parseInt(st.nextToken());
matrix = new RationalNumber[numberOfEquations][numberOfUnknowns+1];

//From String to matrix.
for(int i =0; i<matrix.length;i++)
{
input = scan.nextLine();
while(input.equals(""))
input = scan.nextLine();

st = new StringTokenizer(input);
for(int j =0; j<matrix[0].length; j++)
{
matrix[i][j] = new RationalNumber(st.nextToken());
}
}

//special case.
/*if(numberOfUnknowns == 1 || numberOfEquations == 1)
{
System.out.println();
System.out.println("Solution for Matrix System # "+counter);
System.out.println("x[1] = " + matrix[0][1].div(matrix[0][0]));
continue;
}*/

//the R-Form.
int j = -1;
for(int i=0;i<matrix.length;i++)
{
if(j!=i-1)
j++;
else
j=i;

if(j>=matrix[0].length)
break;

//Sort Matrix.
if(matrix[i][j].equals(new RationalNumber(0)))
{

RationalNumber[] line = new RationalNumber[matrix[0].length];
//Copy to Line
for(int col = 0; col<matrix[0].length;col++)
{
line[col] = matrix[i][col];
}

boolean found = false;
int secondRow;
int secondCol;
for(secondCol =j;secondCol<matrix[0].length&&!found;secondCol++)
{
for(secondRow = i; secondRow<matrix.length&&!found;secondRow++)
{
if(!matrix[secondRow][secondCol].equals(new RationalNumber(0))&&secondRow!=i)
{
found = true;
for(int col = 0; col<matrix[0].length;col++)
{
matrix[i][col] = matrix[secondRow][col];
matrix[secondRow][col] = line[col];
}
j=secondCol;
break;
}
else if(!matrix[secondRow][secondCol].equals(new RationalNumber(0))&&secondRow==i)
{
j = secondCol;
found = true;
break;
}
}
}
}

if(i>=matrix.length||j>=matrix[0].length)
break;

RationalNumber upperRow = matrix[i][j];
RationalNumber lowerRow = null;

if(upperRow.equals(new RationalNumber(0)))
continue;

// Set first element in line to 1
factor = new RationalNumber(matrix[i][j].denom, matrix[i][j].num);
for (int k = i; k < matrix[0].length; k++)
{
matrix[i][k].mul(factor);
}

for(int row=i+1;row<matrix.length;row++)
{
lowerRow = null;
for(int col=j; col<matrix[0].length; col++)
{
if(lowerRow == null)
{
lowerRow = matrix[row][col];
if(lowerRow.equals(new RationalNumber(0)))
break;
}
RationalNumber upperRowValue = matrix[i][col].mul(lowerRow).cancel();
RationalNumber lowerRowValue = matrix[row][col].mul(upperRow).mul(new RationalNumber(-1)).cancel();
matrix[row][col] = lowerRowValue.add(upperRowValue).cancel();
}
}
}

/*System.out.println("After-R "+counter);
for(int i=0;i<matrix.length;i++)
{
for(int lol=0;lol<matrix[0].length;lol++)
{
System.out.print(matrix[i][lol] + " ");
}
System.out.println();
}
System.out.println();*/

rang = 0;
boolean noSolution = false;
//Check Matrix for empty Rows.
for(int row = 0; row<matrix.length;row++)
{
int zeroCounter = 0;
for(int col = 0; col<matrix[0].length-1; col++)
{
if(matrix[row][col].equals(new RationalNumber(0)))
{
zeroCounter++;
}
}
if(zeroCounter == numberOfUnknowns)
{
if(!matrix[row][matrix[0].length-1].equals(new RationalNumber(0)))
{
noSolution = true;
}
}
else
{
rang++;
}
}

System.out.printf("Solution for Matrix System # %d\n", counter);

if(noSolution)
{
System.out.println("No Solution.");
System.out.println();
continue;
}
else if(numberOfUnknowns>rang)
{
System.out.printf("Infinitely many solutions containing %d arbitrary constants.\n", (numberOfUnknowns - rang));
System.out.println();
continue;
}

//Gauß-Jordan
matrix[numberOfUnknowns-1][numberOfUnknowns]=matrix[numberOfUnknowns-1][numberOfUnknowns].div(matrix[numberOfUnknowns-1][numberOfUnknowns-1]);
matrix[numberOfUnknowns-1][numberOfUnknowns-1] = new RationalNumber(1);

for(int i=numberOfUnknowns-1;i>0;i--)
{
RationalNumber lowerRow = matrix[i][i];
RationalNumber upperRow = null;

for(int row =i-1;row>=0;row--)
{
upperRow = null;
for(int col=0;col<matrix[0].length;col++)
{
if(upperRow == null)
upperRow = matrix[row][i];

RationalNumber upperRowValue = matrix[row][col].mul(lowerRow).cancel();
RationalNumber lowerRowValue = matrix[i][col].mul(upperRow).mul(new RationalNumber(-1)).cancel();
matrix[row][col] = upperRowValue.add(lowerRowValue).cancel();
}
}
}
for(int i=0;i<numberOfUnknowns;i++)
{
matrix[i][matrix[0].length-1] = matrix[i][matrix[0].length-1].div(matrix[i][i]).cancel();
matrix[i][i] = new RationalNumber(1);
}

//Last Output.
for(int row =0;row<matrix[0].length-1;row++)
{
System.out.printf("x[%d] = %s\n", row + 1, matrix[row][matrix[0].length-1].toString());
}

System.out.println();

}
while(true);
}
}



3.

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, WS10/11
* Problem: 10109 Solving Systems of Linear Equations
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=13&page=show_problem&problem=1050
*
* @author Fabian Liebl
* @version 1.0, 10/06/2010
*
* Method : Gaussian elimination
* Status : Accepted
* Runtime: 1.060
*/

import java.io.*;
import java.util.Arrays;

public class Main {

private static class RationalNumber {
private long num;
private long denom;

public RationalNumber(long num, long denom) {
this.num = num;
this.denom = denom;
}

public RationalNumber(RationalNumber other) {
this.num = other.num;
this.denom = other.denom;
}

public RationalNumber(String s) {
s = s.trim();
if (s.contains("/")) {
String[] spl = s.split("/");
num = Integer.parseInt(spl[0]);
denom = Integer.parseInt(spl[1]);
} else {
num = Integer.parseInt(s);
denom = 1;
}
}

public void scale(long i) {
num *= i;
denom *= i;
}

public void cancel() {
long i = gcd(num, denom);
num /= i;
denom /= i;
if (denom < 0) {
num *= -1;
denom *= -1;
}
}

public void add(RationalNumber x) {
long d = denom;
this.scale(x.denom);
x.scale(d);
this.num += x.num;
this.cancel();
}

public void mul(RationalNumber x) {
this.num *= x.num;
this.denom *= x.denom;
this.cancel();
}

public void div(RationalNumber x) {
this.num *= x.denom;
this.denom *= x.num;
this.cancel();
}

private long gcd(long a, long b) {
if (b == 0)
return a;
else
return gcd(b, a % b);
}

public String toString() {
if (denom == 1) {
return num + "";
} else {
return num + "/" + denom;
}
}
}

public static void main(String[] args) throws IOException {
BufferedReader inputReader = new BufferedReader(new InputStreamReader(System.in));

int tc = Integer.parseInt(inputReader.readLine());
int unknowns, equations;
RationalNumber[][] A;
RationalNumber[] line;
RationalNumber[] solution;
RationalNumber factor;
RationalNumber temp;

int rank;
boolean zeroline;
boolean incons;
boolean start = true;

String[] s;

while (tc > 0) {
s = inputReader.readLine().split(" ");
unknowns = Integer.parseInt(s[0]);
equations = Integer.parseInt(s[1]);
A = new RationalNumber[equations][unknowns + 1];
line = new RationalNumber[unknowns + 1];
solution = new RationalNumber[unknowns];

for (int i = 0; i < equations; i++) {
s = inputReader.readLine().split(" ");
int sIndex = 0;
for (int j = 0; j < unknowns + 1; j++) {
while (s[sIndex].equals(""))
sIndex++;
A[i][j] = new RationalNumber(s[sIndex]);
sIndex++;
}
}

for (int i = 0; i < equations; i++) {
if (i >= unknowns)
break;
if (A[i][i].num == 0) {
// Find line with element i not 0
for (int j = i; j < equations; j++) {
if (A[j][i].num != 0) {
// Switch lines
line = Arrays.copyOf(A[i], unknowns + 1);
A[i] = Arrays.copyOf(A[j], unknowns + 1);
A[j] = Arrays.copyOf(line, unknowns + 1);
break;
}
}
}
if (A[i][i].num == 0) {
continue; // Only zeros on this column, nothing to do
}

// Set first element in line to 1
factor = new RationalNumber(A[i][i].denom, A[i][i].num);
for (int j = i; j < unknowns + 1; j++) {
A[i][j].mul(factor);
}

// Eliminate column
for (int j = i + 1; j < equations; j++) {
factor = new RationalNumber(A[j][i].num * -1, A[j][i].denom);
factor.div(A[i][i]);
for (int k = i; k < unknowns + 1; k++) {
temp = new RationalNumber(A[i][k]);
temp.mul(factor);
A[j][k].add(temp);
}
}
}

// Confirm consistency
rank = equations;
incons = false;
for (int i = equations - 1; i >= 0; i--) {
zeroline = true;
for (int j = 0; j < unknowns + 1; j++) {
if (A[i][j].num != 0) {
if (j == unknowns) {
incons = true;
break;
}
zeroline = false;
break;
}
}
if (incons) {
break;
}
if (zeroline) {
rank--;
} else {
break;
}
}

if (!start) {
System.out.println();
} else {
start = false;
}
System.out.printf("Solution for Matrix System # %d\n", tc);

if (incons) {
System.out.println("No Solution.");
} else {
if (unknowns > rank) {
System.out.printf("Infinitely many solutions containing %d arbitrary constants.\n", unknowns - rank);
} else {
for (int i = unknowns - 1; i >= 0; i--) {
for (int j = i + 1; j < unknowns; j++) {
temp = new RationalNumber(A[i][j].num * -1, A[i][j].denom);
temp.mul(solution[j]);
A[i][unknowns].add(temp);
}
solution[i] = new RationalNumber(A[i][unknowns]);
}
for (int i = 0; i < unknowns; i++) {
System.out.printf("x[%d] = %s\n", i + 1, solution[i].toString());
}
}
}

inputReader.readLine();
tc = Integer.parseInt(inputReader.readLine());
}
}

}