== include(page="template/taskheader" task_id="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 <= ri < pi, 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 pi este diferit de ri, pentru orice i de la 1 la K. Considerăm şirul sortat al numerelor naturale libere de resturi.
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.
h2. Date de intrare
Fişierul de intrare $resturi2.in$ ...
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.
h2. Date de ieşire
În fişierul de ieşire $resturi2.out$ ...
Fişierul resturi.out conţine pe prima linie un singur număr $M$, reprezentând al $N$-lea număr din şirul considerat.
h2. 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).
h2. Exemplu
table(example). |_. resturi2.in |_. resturi2.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
| 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, …
h3. Explicaţie
table(example). |_. 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, …
== include(page="template/taskfooter" task_id="resturi2") ==
