blob: 6d9490fbed4dbf5eaf17c87afe4e8557aec8b309 (
plain)
1
2
3
4
5
6
7
8
9
10
11
|
//Accepted in Aufgabe mit Forderung: |X|+|Y| minimal (primaer) und X<=Y (sekundaer)
//hab aber keinen Beweis dafuer :)
ll x, y, d; //a * x + b * y = d = ggT(a,b)
void extendedEuclid(ll a, ll b) {
if (!b) {
x = 1; y = 0; d = a; return;
}
extendedEuclid(b, a % b);
ll x1 = y; ll y1 = x - (a / b) * y;
x = x1; y = y1;
}
|
