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;

}