1.

/**
 * ACM Training 2009
 * ACM Problem #10104 - Euclid Problem
 * Link:
 *
 * @author Felix Dietrich
 * @version 1.0, 09/21/2009
 *
 * Methode: Extended euclid algorithm
 * Status : Accepted
 * Runtime: 2.904
 */

import java.util.*;

public class Main
{
    public static void main(String... s)
    {
        Scanner sc = new Scanner(System.in);
        int a,b;
        int[] toPrint;
        
        while(sc.hasNext())
        {
            a = sc.nextInt();
            b = sc.nextInt();
            toPrint = euclid(a,b);
            System.out.println(String.format("%d %d %d", toPrint[1], toPrint[2], toPrint[0]));
        }
    }

    /**
     * extended_euclid(a,b)
1  wenn b = 0
2      dann return (a,1,0)
3  (d',s',t') \leftarrow extended_euclid(b, a mod b)
4  (d,s,t) \leftarrow (d',t',s' - floor(a/b)t')
5  return (d,s,t)


     * @param a
     * @param b
     */
    private static int[] euclid(int a, int b)
    {
        int[] result = new int[3];
        int temp;
        
        if(b == 0)
        {
            result[0] = a;
            result[1] = 1;
            result[2] = 0;
            return result;
        }
        result = euclid(b, a%b);
        result[0] = result[0];
        temp = result[1];
        result[1] = result[2];
        result[2] = temp - (int)Math.floor(a/b)*result[2];
        return result;
    }

    private static void print(int a, int i, int j) {
        // TODO Auto-generated method stub
        
    }
        
}

2.

1.

/**
* 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");

}
}

}


3.


/**
* 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;

}