Cod sursa(job #2585400)

Utilizator sulzandreiandrei sulzandrei Data 19 martie 2020 00:43:48
Problema Algoritmul lui Euclid extins Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 1.8 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 long x;
        public long y;
        public long d;

        public Ecuation() {

        }

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


    }

    private static void euclid_extended(final long a, final long 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 long a;
            final long b;
            final long 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();

    }
}