Cod sursa(job #2585401)

Utilizator sulzandreiandrei sulzandrei Data 19 martie 2020 00:45:21
Problema Algoritmul lui Euclid extins Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 1.79 kb
package ro.infoarena.arhiva.educationala.euclidextins;

import java.io.FileInputStream;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Scanner;

public class Main {


    private static class Ecuation {
        public int x;
        public int y;
        public int d;

        public Ecuation() {

        }

        public Ecuation(final int x, final int y, final int d) {
            this.x = x;
            this.y = y;
            this.d = d;
        }


    }

    private static void euclid_extended(final int a, final int b, final Ecuation ecuation) {
        if (b == 0) {
            ecuation.x = 1;
            ecuation.y = 0;
            ecuation.d = a;
            return;
        }

        final Ecuation ecuation0 = new Ecuation();
        euclid_extended(b, a % b, ecuation0);
        ecuation.x = ecuation0.y;
        ecuation.y = ecuation0.x - (a / b) * ecuation0.y;
        ecuation.d = ecuation0.d;

    }

    public static void main(final String[] args) throws IOException {

        final Scanner in = new Scanner(new FileInputStream("euclid3.in"));
        final PrintWriter out = new PrintWriter("euclid3.out");
        int t = in.nextInt();
        while (t-- > 0) {
            final int a;
            final int b;
            final int c;

            a = in.nextInt();
            b = in.nextInt();
            c = in.nextInt();
            final Ecuation ecuation = new Ecuation(a, b, 1);
            euclid_extended(a, b, ecuation);
            if (c % ecuation.d != 0) {
                out.printf("0 0 \n");
            } else {
                final long x = ecuation.x * (c / ecuation.d);
                final long y = ecuation.y * (c / ecuation.d);
                out.printf("%d %d \n", x, y);
            }


        }
        out.flush();
        out.close();

    }
}