/**

* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, SS10

* Problem: 10104 Euclid Problem

* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=13&page=show_problem&problem=1045

* @author Viktoriya Ryabova

* @version 1.0, 4/7/2010

*

* Method : Ad-Hoc

* Status : accepted

* Runtime: 2.196

*/

import java.util.Scanner;

 

public class Main {

 

public static void main(String[] args) {

Scanner sc = new Scanner (System.in);

while(sc.hasNext()){

// 2 werte einlesen

int a = sc.nextInt();

int b= sc.nextInt();

int d [] = gcd (a,b);

// gefundene werte in richtige reihenfolge ausgeben

System.out.println(d[1]+" "+d[2]+" "+d[0]);

}

}

public static int [] gcd (int p, int q){

if (q==0){

// als array zurückgeben

return new int []{p, 1, 0};

}

else{

// wenn zweites komponent nicht null ist, die komponenten

// werden getauscht,und zweite komponent = rest von telung des

// ursprunglichen kmponenten

int [] zurueck = gcd (q, p % q);

int d = zurueck [0];

int a = zurueck [2];

int b = zurueck [1] - (p / q) * zurueck [2];

return new int []{d, a, b};

}

}

}

2.


/**
 * FWP, Ausgewählte Probleme aus dem ACM Programming Contest, SS10
 * Problem: 10104 - Euclid Problem
 * Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=13&page=show_problem&problem=1045
 *
 * @author Siegfried Ippisch
 * @version 1.0 27.06.2010
 *
 * Method : recursive
 * Status : Accepted
 * Runtime: 2.076
 */


import java.util.Scanner;

public class EuclidProblem {
   
    private static class Result{
        int x,y,d;
        Result(int x, int y, int d){
            this.d = d;
            this.x = x;
            this.y = y;
        }
        public String toString(){
            return x + " " + y + " " + d;
        }
    }
   
    private static Result euclid(int a, int b){
       
        int q = a/b;
        int r = a%b;
       
        if(r == 0){
            return new Result(0,1,b); // q*a + 1*b = b
        }
       
        Result res = euclid(b,r);
        int x = res.x;
        res.x = res.y;
        res.y = x - res.y * q;
       
        return res;
    }
   
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
       
        while(in.hasNext()){
            System.out.println(euclid(in.nextInt(),in.nextInt()));
        }
    }
   
}

3.

/**
* Angewandte Mathematik, SS09, IFB 2C
* ACM Problem #10104 - Euclid Problem
* Link: http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=13&problem=1045&mosmsg=Submission+received+with+ID+7043086
*
* @author Andre Wolfram
* @author Christoph Miesel
* @author Robert Seilbeck
* @version 1.0, 04/01/2009
*
* Status : Accepted
* Runtime 2.540
*/


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;


public class Main {

/**
* @param args
* @throws IOException
* @throws NumberFormatException
*/
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(
System.in));
String line;
int x = 0;
int lastx = 1;
int y = 1;
int lasty = 0;

while ((line = reader.readLine()) != null) {
StringTokenizer st=new StringTokenizer(line," ");

int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());

x = 0;
lastx = 1;
y = 1;
lasty = 0;
//Algorithmus nach Wikipedia http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm
while (b != 0){
int quotient = a / b;

int temp = b;
b = a % b;
a = temp;

temp = x;
x = lastx-quotient*x;
lastx = temp;

temp = y;
y = lasty-quotient*y;
lasty = temp;
}
System.out.printf(lastx+" "+lasty+" "+a+"\n");

}
}

}


4.


/**
* Angewandte Mathematik SS 09
10104 Euclid Problem
* UVa Status: Accepted, 21.03.2009
* Run Time: 0.290
* Programming Language: C
* @author Doina Logofatu logofatu@hm.edu
*/

#include <stdio.h>
#include <math.h>

int main() {

long a, b;
long x, y, lastx, lasty, temp, q;

while( scanf("%ld %ld", &a, &b) == 2){
x = lasty = 0;
y = lastx = 1;
while(b){
temp = b;
q = a / b;
b = a % b;
a = temp;

temp = x;
x = lastx - q*x;
lastx = temp;

temp = y;
y = lasty - q*y;
lasty = temp;
}
printf("%ld %ld %ld\n", lastx, lasty, a);
}

return 0;

}