gcdx.cpp

Ugrás a fájl dokumentációjához.

#include<iostream>
using namespace std;
#include "gcdx.h"
 
namespace bme {
 
    int gcdx(int a, int b, int& x, int& y) {
        // Ha mind a, mind b 0, akkor irjunk ki hibát, és térjünk vissza 0-val:
        if ((a == 0) && (b == 0)) {
            cerr << "WARNING: gcd called with both arguments equal to zero." << endl;
            x = 0;
            y = 0;
            return 0;
        }
 
        //ha b=0, akkor gcd(a,b) = |a|, x= 1 vagy -1, y tetszőleges (pl. 0)
        if (b == 0) {
            y = 0;
            if (a < 0) {
                x = -1;
                return -a;
            }
            else {
                x = 1;
                return a;
            }
        }
 
        int d = 0; //ebben tároljuk majd a vissztérési értéket, azaz a legnagyobb közös osztót
 
        //ha b negatív, akkor megoldjuk a feladatot (-b)-re
        if (b < 0) {
            d = gcdx(a, -b, x, y);
            y = -y;
            return d;
        }
 
        //ha a negatív, akkor megoldjuk a feladatot (-a)-ra
        if (a < 0) {
            d = gcdx(-a, b, x, y);
            x = -x;
            return d;
        }
 
        //ezen a ponton b pozitív, a nemnegatív
        int aa = b;
        int bb = a % b;
        int qq = a / b;
        int xx = 0; 
        int yy = 0;
 
        d = gcdx(aa, bb, xx, yy);
        
        x = yy;
        y = xx - qq * yy;
 
        return d;
    }
 
}