Cod sursa(job #1463988)

Utilizator prsadrianAdrian Peres prsadrian Data 21 iulie 2015 23:33:26
Problema Algoritmul lui Euclid extins Scor 10
Compilator java Status done
Runda Arhiva educationala Marime 1.33 kb
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Scanner;

public class Main {
	
	public static int gcd(int a, int b) {
		if (b == 0)
			return a;
		return gcd(b, a % b);
	}
	
	public static int[] extendedGCD(int a, int b) {
		if(b==0) 
			return new int[] {a, 1, 0};
		int[] values = extendedGCD(b, a % b);
		int d = values[0];
		int x = values[2];
		int y = values[1] - (a/b) * values[2];
		return new int[] {d, x, y};
	}

	public static void main(String[] args) throws IOException {
		Scanner reader = new Scanner(new FileInputStream("euclid3.in"));
		PrintWriter writer = new PrintWriter("euclid3.out");
		
		int ecuations = reader.nextInt();
		int a = 0;
		int b = 0;
		int c = 0;
		for (int i = 0; i < ecuations; i++) {
			a = reader.nextInt();
			b = reader.nextInt();
			c = reader.nextInt();
			
			int d = gcd(a,b);
			boolean flag = ((c % d) == 0);
			
			if(flag == true) {
//				a = a * (c / d);	System.out.println(a);
//				b = b * (c / d);	System.out.println(b);
				int[] result = extendedGCD(a,b);
				writer.write((result[1] * (c/d)) + " " + (result[2] * (c/d)) + "\n");
			}
			
			if(flag == false) {
				writer.write(0 + " " + 0);
			}
			
		}
		reader.close();
		writer.close();
		
	}
}