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, programul va rula.

În cazul în care datele nu respectă restricțiile, 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

Intrare

6 14

Ieșire

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

if __name__ == '__main__':

   x, y = map(int, input("Introduceti cele doua numere:").split())
   if not validate_input(x, y):
       print("Input invalid!")
   else:
       # calculam gcd si lcm dintre X si Y
       def gcd(a, b):
           while b:
               a, b = b, a % b
           return a

       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)

</syntaxhighlight>

Explicatie cod:

Această porțiune de cod este o funcție de validare numită validate_input(x, y) care primește două numere x și y și verifică dacă acestea sunt numere naturale mai mici decât 1.000.000.001. Dacă nu sunt îndeplinite aceste condiții, funcția va returna False, altfel va returna True.

Apoi, codul verifică dacă acesta este rulat ca program principal (adică nu este importat ca modul într-un alt program) utilizând construcția if __name__ == '__main__':.

În cadrul acestei construcții, se citesc cele două numere de la tastatură utilizând funcția input() și map(), apoi se validează inputul folosind funcția validate_input(x, y). Dacă inputul este invalid, se afișează un mesaj de eroare, altfel, se calculează gcd_xy și lcm_xy dintre x și y, iar apoi se iterează prin toate numerele între 1 și gcd(X, Y) pentru a găsi valoarea lui k care produce cel mai mic multiplu comun al numerelor x + k și y + k. Valoarea lui k este afișată la sfârșit.