Cod sursa(job #2224597)

Utilizator radustn92Radu Stancu radustn92 Data 24 iulie 2018 16:25:21
Problema Algoritmul lui Euclid extins Scor 100
Compilator java Status done
Runda Arhiva educationala Marime 3.25 kb
import java.io.*;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        InputStream inputStream = new FileInputStream("euclid3.in");
        OutputStream outputStream = new FileOutputStream("euclid3.out");

        try (InputReader inputReader = new InputReader(inputStream);
             PrintWriter printWriter = new PrintWriter(outputStream)) {
            new Solver(inputReader, printWriter).solve();
        }
    }

    static class Solver {

        private InputReader inputReader;

        private PrintWriter printWriter;

        public Solver(InputReader inputReader, PrintWriter printWriter) {
            this.inputReader = inputReader;
            this.printWriter = printWriter;
        }

        public void solve() {
            int noTests = inputReader.nextInt();
            for (int testNo = 0; testNo < noTests; testNo++) {
                int a = inputReader.nextInt(), b = inputReader.nextInt(), c = inputReader.nextInt();
                // solve equation a * x + b * y = c

                Solution sol = findSolution(a, b);
                if (c % sol.gcd != 0) {
                    printWriter.println("0 0");
                } else {
                    int mulFactor = c / sol.gcd;
                    printWriter.printf("%d %d\n", sol.x * mulFactor, sol.y * mulFactor);
                }
            }
        }

        // a solution respects the property: a * x + b * y = cmmdc(a, b)
        private Solution findSolution(int a, int b) {
            if (b == 0) {
               return new Solution(1L, 0L, a);
            }

            Solution nextStepSolution = findSolution(b, a % b);
            // a solution (x0, y0) for b * x0 + a % b * y0 can be used to find a solution for (a, b)
            // by grouping factors together:
            // b * x0 + (a - [a / b] * b) * y0 = d <=> a * y0 + b * (x0 - [a / b] * y0) = d
            long currX = nextStepSolution.y;
            long currY = nextStepSolution.x - (long) a / b * nextStepSolution.y;

            return new Solution(currX, currY, nextStepSolution.gcd);
        }
    }

    static class Solution {
        public long x, y;
        int gcd;

        public Solution(long x, long y, int gcd) {
            this.x = x;
            this.y = y;
            this.gcd = gcd;
        }
    }

    static class InputReader implements AutoCloseable {

        private BufferedReader bufferedReader;

        private StringTokenizer stringTokenizer;

        public InputReader(InputStream inputStream) {
            bufferedReader = new BufferedReader(new InputStreamReader(inputStream));
            stringTokenizer = null;
        }

        private String nextToken() {
            if (stringTokenizer == null || !stringTokenizer.hasMoreTokens()) {
                try {
                    stringTokenizer = new StringTokenizer(bufferedReader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }

            return stringTokenizer.nextToken();
        }

        private int nextInt() {
            return Integer.parseInt(nextToken());
        }

        @Override
        public void close() throws IOException {
            bufferedReader.close();
        }
    }
}