Fişierul intrare/ieşire:resturi2.in, resturi2.outSursăLot Alba Iulia 2004
AutorTiberiu DanetAdăugată defanache99Constantin-Buliga Stefan fanache99
Timp execuţie pe test0.2 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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.inresturi2.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.inresturi2.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, …

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?