1237 - Numereiajb

Cerinta

Numerele iajb sunt numerele care pot fi scrise sub forma i * a + j * b, cu i și j numere naturale și i + j > 0.

Cunoscând a și b și un număr n, să se determine valorile i și j pentru care se vor forma primele n numere iajb in ordine crescătoare.

Date de intrare

Fișierul de intrare numereiajb.in conține pe prima linie numărul 3 numere naturale a, b și n, având semnificațiile de mai sus.

Date de iesire

Fișierul de ieșire numereiajb.out va conține pe cele n linii câte o pereche de numere naturale i și j care răspund cerinței.

Restricții și precizări

• 1 ≤ n ≤ 2.000.000 (!)
• 1 ≤ a, b ≤ 50.000
• Dacă un număr iajb se obține din perechi diferite de (i, j) atunci se va afișa doar cea cu i-ul minim

Exemplul 1

numereiajbin.txt

2 3 5

numereiajbout.txt

Datele introduse corespund restrictiilor impuse.

1 0

0 1

2 0

1 1

0 2

Exemplul 2

numereiajbin.txt

-1 2 0

numereiajbout.txt

Datele introduse nu corespund restrictiilor impuse.

Rezolvare

<syntaxhighlight lang="python3" line="1">

def generare_numere_iajb(a, b, n):

   rezultate = []
   for i in range(1, n+1):
       for j in range(1, i+1):
           numar = i * a + j * b
           rezultate.append((numar, i, j))

   rezultate.sort()
   return rezultate[:n]

1. Exemplu de utilizare

a = 2 b = 3 n = 5

rezultate = generare_numere_iajb(a, b, n) print(f"Primele {n} numere iajb pentru a={a} și b={b}: {rezultate}")

</syntaxhighlight>