Pagini recente » Cod sursa (job #1676068) | Cod sursa (job #2757482) | Cod sursa (job #1582104) | Cod sursa (job #1834184) | Cod sursa (job #2224597)
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();
}
}
}