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

<syntaxhighlight lang="python" line>

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