1.

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, WS09
* Problem: 10104 Euclid Problem
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=13&problem=1045&mosmsg=Submission+received+with+ID+7498993
*
* @author Stefan Gohlke
* @version 1.0, 10/21/2009
*
* Method : Ad-Hoc
* Status : Accepted
* Runtime: 2.440
*/

package euklid_acc;

import java.util.Scanner;

public class Main {

public static void main (String[] args)
{
extendedEuclid();
}

public static void extendedEuclid()
{
Scanner scanner = new Scanner(System.in);
int zahl1 = 0;
int zahl2 = 0;

while (scanner.hasNextInt())
{
zahl1 = scanner.nextInt();
zahl2 = scanner.nextInt();

if (zahl1 < 1000000001 && zahl2 < 1000000001)
{
long[] ergbnisarray = gcd(zahl1, zahl2);
System.out.println(ergbnisarray[0] + " " + ergbnisarray[1] + " " + ergbnisarray[2]);
}
}
}

public static long[] gcd(long a, long b) {

long x = 0;
long lastx = 1;
long y = 1;
long lasty = 0;
long quotient;
long temp;

while (b != 0)
{
quotient = a / b;
temp = b;
b = a % b;
a = temp;

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

temp = y;
y = lasty-quotient*y;
lasty = temp;
}

long[] rueck = new long[3];
rueck[0] = lastx;
rueck[1] = lasty;
rueck[2] = a;

return rueck;
}
}