Editing 2950 - Adun

Sursa: [https://www.pbinfo.ro/probleme/4273/prodpp]
== Cerinţa ==

Ionel a primit la ora de matematica o problema interesantă. El are doua numere naturale '''X''' și '''Y''' și trebuie să determine un număr natural '''K''' astfel încât cel mai mic multiplu comun al numerelor '''X + K''' și '''Y + K''' să fie minim


Determinați valoarea lui '''K''' astfel încât cel mai mic multiplu comun al numerelor '''X + K''' și '''Y + K''' să fie minim.

== Date de intrare ==
Programul citește de la tastatură numerele naturale '''X și Y''' separate cu un spațiu.

== Date de ieșire == 
Programul va afișa pe ecran valoarea '''K'''.

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect.", apoi pe un rând nou afișează valoarea lui K astfel încât cel mai mic multiplu comun al numerelor X + K și Y + K să fie minim. 

În caz contrar, se va afișa pe ecran: "Datele nu corespund restricțiilor impuse."

== Restricţii şi precizări ==
'''X și Y''' sunt numere naturale mai mici decât 1.000.000.001.

Dacă sunt mai multe valori K pentru care cel mai mic multiplu comun al numerelor '''X + K și Y + K''' este minim, se va afișa valoarea '''K minimă'''.

== Exemplul 1 ==
; Datele de intrare
: Introduceti cele doua numere:
: 6 14
; Datele de ieșire
: Datele sunt introduse corect.
: 2
<br>

== Rezolvare == 
<syntaxhighlight lang="python" line>
#2950
def validate_input(x, y):
    if x < 1 or x >= 1000000001:
        return False
    if y < 1 or y >= 1000000001:
        return False
    return True


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def solve(x, y):
    gcd_xy = gcd(x, y)
    lcm_xy = x * y // gcd_xy

    # iteram prin toate numerele intre 1 si gcd(X, Y)
    min_lcm = lcm_xy
    min_k = 0

    for k in range(1, gcd_xy + 1):
        lcm_k = (x + k) * (y + k) // gcd(x + k, y + k)
        if lcm_k < min_lcm:
            min_lcm = lcm_k
            min_k = k

    # afisam valoarea lui K
    print(min_k)


if __name__ == '__main__':
    x, y = map(int, input("Introduceti cele doua numere:").split())

    if not validate_input(x, y):
        print("Datele nu corespund restricțiilor impuse.")
    else:
        print("Datele sunt introduse corect.")
        solve(x, y)

</syntaxhighlight>

'''Explicatie cod:'''

Această implementare calculează cel mai mic multiplu comun al două numere naturale x și y, în care sunt adăugate valori constante diferite k la fiecare număr și se determină valoarea minimă a lui k astfel încât LCM(x+k, y+k) să fie minim.

Funcția `validate_input(x, y)` verifică dacă cele două numere introduse sunt numere naturale și se încadrează în intervalul [1, 1000000000]. Dacă una dintre condiții nu este îndeplinită, funcția returnează `False`.

Funcția `gcd(a, b)` calculează cel mai mare divizor comun al două numere a și b folosind algoritmul lui Euclid.

Funcția `solve(x, y)` calculează cel mai mic multiplu comun al lui x și y folosind gcd și apoi calculează pentru fiecare valoare k între 1 și gcd(x, y) valoarea LCM(x+k, y+k) și determină valoarea minimă a lui k astfel încât LCM(x+k, y+k) să fie minim. Valoarea minimă a lui k și LCM(x+k, y+k) sunt stocate în variabilele `min_k` și `min_lcm`. La sfârșit, funcția afișează valoarea lui `min_k`.

În `main()`, se citește cele două numere de la tastatură folosind `map()` și apoi se verifică dacă datele de intrare sunt corecte folosind funcția `validate_input(x, y)`. Dacă datele de intrare sunt incorecte, se afișează un mesaj corespunzător. În caz contrar, se afișează un mesaj de confirmare și se apelează funcția `solve(x, y)`.