### Legnagyobb közös osztó
### ======================


### ---------------------------------------------------------------------------
### 1. feladat: Euklideszi algoritmus
###
### Számítsuk ki adott a és b természetes számok legnagyobb közös osztóját
### az euklideszi algoritmussal.

def eukl_alg_hosszu (a, b):
    while b != 0:
    	t = b
    	b = a % b
    	a = t
    return a

def eukl_alg (a, b):
    while b != 0:
    	a, b = b, a % b   # szimultán értékadás (a = b és b = a % b)
    return a

def test1 ():
    print("1. Euklideszi algoritmus")
    for a in range(1, 51):
        for b in range(1, 51):
            g = gcd(a, b)
            assert eukl_alg(a, b) == g, f"eukl_alg({a}, {b}) != {g}"
    for (a,b) in [
        (50, 22),
        (2^20, factorial(10)),
        (165580141, 102334155),
        (33333333333, 1111111111),
    ]:
        print(f"eukl_alg({a}, {b}) ==", eukl_alg(a, b))
    print()
test1()


### ---------------------------------------------------------------------------
### 2. feladat: Bővített euklideszi algoritmus
###
### Implementáljuk a bővített euklideszi algoritmust a tanult módon.
### Az eredmény egy (g, x, y) hármas, ahol g a bemenő két szám legnagyobb közös
### osztója, x és y pedig Bézout-együtthatóik.

def bov_eukl_alg (a, b):
    pass #TODO

def test2 ():
    print("2. Bővített euklideszi algoritmus")
    for a in range(1, 31):
        for b in range(1, 31):
            g, x, y = bov_eukl_alg(a, b)
            assert g == gcd(a, b), f"bov_eukl_alg({a}, {b})"
            assert x*a + y*b == g
    print("(50, 22) ->", bov_eukl_alg(50, 22))
    print("(16, 10) ->", bov_eukl_alg(16, 10))
    print()
#test2()


### ---------------------------------------------------------------------------
### 3. feladat: Lineáris diofantikus egyenlet
###
### Oldjuk meg az ax + by = c lineáris diofantikus egyenletre az alábbi
### feladatokat, ahol a, b és c az egyenlet paraméterei (pozitív egész számok).
### (A megoldáshoz ne használjunk solve()-ot vagy hasonló Sage függvényt.)

### a) Számítsuk ki az egyenlet _egyik_ megoldását (egy (x,y) párt). Ha nincs
### megoldás, None-t adjunk vissza.
def lin_diof_1 (a, b, c):
    pass #TODO

### b) Számítsuk ki az egyenlet n egymást követő megoldását egy listában:
### [(x1,y1), (x2,y2), ..., (xn,yn)]. (Ha nincs megoldás, üres listát adjunk.)
def lin_diof_n (a, b, c, n):
    pass #TODO

### c) Számítsuk ki az összes nemnegatív megoldást egy listában.
def lin_diof_nneg (a, b, c):
    pass #TODO

def test3 ():
    print("3. Lineáris diofantikus egyenlet")
    for a,b,c in [
        (39, 15, 6),
        (32, 20, 10),
        (12, 7, -4),
        (200, 120, 4000),
        (12, 7, 100),
        (12345678, 89009765, 1122334455667788), # c)-re van "szép" megoldás
    ]:
        print(f"{a}x + {b}y == {c}")
        sol = lin_diof_1(a, b, c)
        print("   a)", sol)
        if sol != None: assert a*sol[0] + b*sol[1] == c
        sol = lin_diof_n(a, b, c, 3)
        if sol != None:
            print("   b)", sol)
            assert len(sol) == 0 or len(sol) == 3, "hibás darabszám"
            for x,y in sol:
                assert a*x + b*y == c, f"({x}, {y}) nem megoldás"
        sol = lin_diof_nneg(a, b, c)
        if sol != None:
            print("   c)", sol)
            for x,y in sol:
                assert x >= 0 and y >= 0, f"({x}, {y}) negatív"
                assert a*x + b*y == c, f"({x}, {y}) nem megoldás"
            if a == 12345678: assert sol, f"kell lennie megoldásnak"
    print()
#test3()


### ---------------------------------------------------------------------------
### 4. feladat: Lnko prímtényezőkből
###
### Számítsuk ki adott a és b természetes számok legnagyobb közös osztóját
### a prímtényezős felbontásuk segítségével.

def gcd_fact (a, b):
    pass

def test4 ():
    print("4. Lnko prímtényezőkből")
    for a in range(1, 51):
        for b in range(1, 51):
            assert gcd_fact(a, b) == gcd(a, b), f"gcd_fact({a}, {b})"
    print(f"gcd_fact(50, 22) ==", gcd_fact(50, 22))
    print(f"gcd_fact(2^20, 10!) ==", gcd_fact(2^20, factorial(10)))
    print()
#test4()


### ---------------------------------------------------------------------------
### 5. feladat: Lnko sebesség
###
### (Ezt a feladatot célszerű saját gépen megoldani, az erőforrásigény miatt.)
### Hasonlítsuk össze a legnagyobb közös osztó fenti kétféle módszerének
### (euklideszi algoritmus és prímtényezős felbontás) sebességét.
### Legyen a és b két-két nagy véletlen prímszám szorzata, pontosabban
### a = p*q és b = p*r, ahol p, q és r három véletlen prímszám.
### A prímszámok 2 és 10^n között lehetnek, ahol n egyre nagyobb kitevő:
### n = 2, 3, 4, ..., 40. (Azaz a és b nagyjából hasonló nagyságrendű lesz,
### és úgy csináltuk, hogy lnko(a, b) = p legyen.)
### Melyik változat a hatékonyabb? Melyik mekkora n-ig használható?

def fel5 ():
    print("5. Lnko sebesség")
    #TODO
#fel5()