2950 - Adun

Sursa: [1]

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

Rezolvare

#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)

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)`.