Cod sursa(job #3268190)

Utilizator lucky1992Ion Ion lucky1992 Data 13 ianuarie 2025 21:51:00
Problema Algoritmul lui Euclid extins Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 1.08 kb
import java.io.*;

public class Main {

  public static int euclid(int a, int b, int[] k) {
    if (b == 0) {
      k[0] = 1;
      k[1] = 0;
      return a;
    }

    int d = euclid(b, a % b, k);
    int t = k[1];
    k[1] = k[0] -  (a/b) * k[1];
    k[0] = t;
    return d;
  }

  public static void main(String[] args) throws IOException {
    try (BufferedReader reader = new BufferedReader(new FileReader("euclid3.in"), 65536);
         BufferedWriter writer = new BufferedWriter(new FileWriter("euclid3.out"))) {
      int T = Integer.parseInt(reader.readLine());

      int[] k = new int[] {0, 0};

      for (int i = 0; i < T; i++) {
        String[] tokens = reader.readLine().split(" ");
        int a = Integer.parseInt(tokens[0]);
        int b = Integer.parseInt(tokens[1]);
        int c = Integer.parseInt(tokens[2]);

        k[0] = 0;
        k[1] = 0;

        int d = euclid(a, b, k);
        if (c % d != 0) {
          writer.write("0 0\n");
        } else {
          int factor = c / d;
          writer.write(k[0] * factor + " " + k[1] * factor + "\n");
        }
      }
    }
  }
}