| Fişierul intrare/ieşire: | resturi2.in, resturi2.out | Sursă | Lot Alba Iulia 2004 |
| Autor | Tiberiu Danet | Adăugată de |  Constantin-Buliga Stefan •fanache99 |
| Timp execuţie pe test | 0.1 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Resturi2
Se dă un număr natural K şi numerele naturale p 1, p 2, …, p K, r 1, r 2, …, r K, unde p 1, …, p K sunt numere prime diferite două câte două şi 0 <= r i < p i, pentru orice i de la 1 la K. Spunem că un număr X este liber de resturi, dacă restul împărţirii lui X la p i este diferit de r i, pentru orice i de la 1 la K. Considerăm şirul sortat al numerelor naturale libere de resturi.
Să se determine al N-lea element al şirului.
Date de intrare
Fişierul resturi.in conţine pe prima linie numerele K şi N, separate printr-un spaţiu. Următoarele K linii conţin perechi de numere p i, r i, separate printr-un spaţiu.
Date de ieşire
Fişierul resturi.out conţine pe prima linie un singur număr M, reprezentând al N-lea număr din şirul considerat.
Restricţii
- 0 ≤ K ≤ 10
- 1 ≤ N ≤ 2 000 000 000
- Şirul considerat este indexat începând de la 1.
- Se garantează că rezultatul va fi mai mic decât 10 000 000 000 (zece miliarde).
Exemplu
| resturi2.in | resturi2.out |
|---|---|
| 3 6 2 1 3 2 5 2 | 18 |
În acest caz, şirul considerat este: 3, 4, 6, 7, 10, 12, 13, 16, 18, 19, 21, 24, 25, 27, 28, 30, 31, …
| resturi2.in | resturi2.out |
|---|---|
| 4 16 3 2 17 9 7 1 23 0 | 30 |
În acest caz, şirul considerat este: 3, 4, 6, 7, 10, 12, 13, 16, 18, 19, 21, 24, 25, 27, 28, 30, 31, …
