045 : Extended Euclidean algorithm

(Briefing)
문제	단 하나의 맥락	입출력과 되어야 하는 그림
Ax + By = C 를 만족하는 (x, y) 쌍을 찾아라		I // A B C O // (존재x) -1 (존재) (x, y)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception {

        // Input Supply Cable
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        // Preprocessing
        int A = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());

        // Operating GCD(1/2)
        long GCD = GCD(Math.max(A, B), Math.min(A, B));

        // Operating Extended Euclidean(2/2) + OE Cable
        if (C % GCD != 0) {
            System.out.println(-1);
        }  else {
            int Quotient = ((int) (C / GCD));
            long [] ret = Extended(A, B);
            System.out.println(ret[0]*Quotient + " " + ret[1]*Quotient);
        }
    }

    // External Module(1/2)
    private static long[] Extended(long A, long B) {
        long [] ret = new long[2];
        if (B == 0) {
            ret[0] = 1; ret[1] = 0;
            return ret;
        }
        long Q = A/B;
        long[] V = Extended(B, A%B);
        ret[0] = V[1];
        ret[1] = V[0] - V[1]*Q;
        return ret;
    }
    
    // External Module(1/2)
    private static long GCD(long B, long S) {
        long r = B % S;
        while (r != 0) {
            r = B%S;
            B = S;
            S = r;
        }
        return Math.abs(B);
    }
}