Cod sursa(job #1848548)

Utilizator vladradu97150Vlad Radu vladradu97150 Data 16 ianuarie 2017 11:09:22
Problema Algoritmul lui Euclid extins Scor 100
Compilator java Status done
Runda Arhiva educationala Marime 1.37 kb
import java.io.BufferedWriter;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.Scanner;

class Main {

	public static void main(String[] args) throws FileNotFoundException, IOException {
		try(FileReader freader = new FileReader("euclid3.in");
			Scanner scanner = new Scanner(freader);
			FileWriter fwriter = new FileWriter("euclid3.out");
			BufferedWriter bwriter = new BufferedWriter(fwriter)) {
				int N = scanner.nextInt();
			for(int i=0;i<N;i++) {
				long a = scanner.nextLong();
				long b = scanner.nextLong();
				long c = scanner.nextLong();
				long s_i_1 = 1L, s_i = 0L, t_i_1 = 0L, t_i = 1L;
				long div = 0, mod = 0;
				if(b == 0) {
					if(c % a == 0) {
						bwriter.write( c/a + " 0");
					} else {
						bwriter.write( "0 0");
					}
					bwriter.newLine();
					continue;
				}
				while(a%b != 0) {
					div = a/b;
					mod = a%b;
					long new_s_i = s_i_1 - div*s_i;
					s_i_1 = s_i;
					s_i = new_s_i;
					long new_t_i = t_i_1 - div*t_i;
					t_i_1 = t_i;
					t_i = new_t_i;
					a = b;
					b = mod;
				}
				if(c%b != 0) {
					bwriter.write("0 0");
					bwriter.newLine();
				} else {
					s_i = s_i*(c/b);
					t_i = t_i*(c/b);
					bwriter.write(s_i + " " + t_i);
					bwriter.newLine();
				}
			}
		}
		
	}

}