1.

/**
* Angewandte Mathematik, SS11
* Problem: 10104 - Euclid Problem
* http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=13&page=show_problem&problem=1045
* @author Sebastian Stumpf
* @author Benjamin Vogt
* @version 1.0, 2011-04-02 09:03:1
*
* Method : Ad-Hoc
* Status : Accepted
* Runtime: 2.148
*/

import java.util.*;
public class Main
{   
//    erweiterter Euklidischer Algorithmus, rekursiv implementiert, gibt, wenn fertig:
//    in result[0]: GCD, result[1]: x, result[2]: y, so dass: Ax + By = GCD!
//    man muss Datentyp long nehmen, da sonst die für int zu verfügung stehende stellenanzahl
//    für die multiplikation nicht mehr ausreicht
    static long[] extendedEuklid(long A, long B)
    {
        if (B == 0)
            return new long[] { A, 1, 0 };
        long[] result = extendedEuklid(B, A % B);
        long d = result[0];
        long a = result[2];
        long b = result[1] - (A / B) * result[2];
        return new long[] { d, a, b };
    }

    public static void main(String[] args)
    {
       
/*        StringBuilder sb = new StringBuilder("");
        for(int i=1; i<=1000; i++)
        {
            sb = sb.append(i+" "+(1000-i)+"\n");
        }
        String s = sb.toString();
*/       
        Scanner scanner = new Scanner(System.in);
        while(true)
        {
            try
            {
                int A = scanner.nextInt();
                int B = scanner.nextInt();
                long[] result = extendedEuklid(A, B);
//                System.out.println(A+" "+B);
                System.out.println(result[1]+" "+result[2]+" "+result[0]);
            }
            catch(NoSuchElementException nsee)
            {
                break;
            }   
        }
    }

}

----------------------------------------------------------------------

1.


/**
 * FWP, Ausgewählte Probleme aus dem ACM Programming Contest, WS10/11
 * Problem: 10104 Euclid Problem
 * Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&page=show_problem&problem=1045
 *
 * @author Patrick Bédat
 * @version 1.0, 10/31/2010
 *
 * Method : Extended Euclid Algorithm
 * Status : Accepted
 * Runtime: 1.464
 */
package euclidProblem;

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

public class Main
{

    public static void main(String... args) throws IOException
    {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String line = reader.readLine();

        while (true)
        {
            StringTokenizer st = new StringTokenizer(line);

            long a = Long.parseLong(st.nextToken());
            long b = Long.parseLong(st.nextToken());

            long gcd = gcd(a, b);

            System.out.println(x + " " + y + " " + gcd);
            //System.out.printf("%d %d %d%n",x, y, gcd);  <--- gives yout TLE!!!wtf?

            if (!reader.ready())
                break;
            line = reader.readLine();
        }
    }
    private static long x = -1;
    private static long y = -1;

    private static long gcd(long a, long b)
    {
        if (b == 0)
        {
            x = 1;
            y = 0;

            return a;
        }
       
        long gcd = gcd(b, a % b);

        long xOld = x;
        x = y;
        y = xOld - a / b * y;

        return gcd;
    }
}


2.

/*
 * ACM Contest training
 * Problem: 10104 - Euclid Problem
 * Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=13&page=show_problem&problem=1045
 *
 * @author Christoph Goettschkes
 * @version 1.0, 10/25/2010
 *
 * Method : Extended Euclid Algorithm http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm
 * Status : Accepted
 * Runtime: 1.504
 */

import java.io.*;
import java.util.*;

class Main
{

    public static void main(String[] args) throws Exception
    {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        String line = reader.readLine();

        while (true) {
            StringTokenizer tokenizer = new StringTokenizer(line);
            long a = Long.parseLong(tokenizer.nextToken());
            long b = Long.parseLong(tokenizer.nextToken());

            long[] result = extended_eculid(a, b);
            System.out.println(result[1] + " " + result[2] + " " + result[0]);

            if (!reader.ready())
                break;
            line = reader.readLine();
        }
    }

    private static long[] extended_eculid(long p, long q) {
        if (q == 0)
            return new long[] { p, 1, 0 };

        long[] vals = extended_eculid(q, p % q);
        long d = vals[0];
        long a = vals[2];
        long b = vals[1] - (p / q) * vals[2];
        return new long[] { 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 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};

}

}

}

3.


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

4.

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

}
}

}


5.


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

}