Algorithm

 problem Link : https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=1045 

From Euclid it is known that for any positive integers A and B there exist such integers X and Y that AX + BY = D, where D is the greatest common divisor of A and B. The problem is to find for given A and B corresponding X, Y and D. Input The input will consist of a set of lines with the integer numbers A and B, separated with space (A, B < 1000000001). Output For each input line the output line should consist of three integers X, Y and D, separated with space. If there are several such X and Y , you should output that pair for which |X| + |Y | is the minimal. If there are several X and Y satisfying the minimal criteria,

output the pair for which X ≤ Y .

Sample Input 4 6 17 17

Sample Output -1 1 2 0 1 17

 

Code Examples

#1 Code Example with C Programming

Code - C Programming

 #include <bits/stdc++.h>
using namespace std;

int x,y,d;

// ax + by = d
// store x, y, and d as global variables
void extendedEuclid(int a, int b) {
    if (b == 0) { x = 1; y = 0; d = a; return; } // base case
    extendedEuclid(b, a % b); // similar as the original gcd
    int x1 = y;
    int y1 = x - (a / b) * y;
    x = x1;
    y = y1;
}

int main() {
    int a,b;
    while(scanf("%d %d",&a,&b) != EOF) {
        extendedEuclid(a,b);
        printf("%d %d %d\n",x,y,d);
    }
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
4 6
17 17

Output

x
–
+
cmd
-1 1 2
0 1 17
Advertisements

Demonstration

UVA Online Judge solution - 10104  -Euclid Problem - UVA Online Judge solution in C,C++,Java

Previous
UVA Online Judge solution - 10102 - The path in the colored field - UVA Online Judge solution in C,C++,Java
Next
UVA Online Judge solution - 10125 - Sumsets - UVA Online Judge solution in C,C++,Java