.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » resturi

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
resturi


Timp maxim de execuţie / test:
0.2s
Memorie totala disponibilă / stivă:
16MB / 1MB

Se dă un număr natural K şi numerele naturale p1, p2, …, pK, r1, r2, …, rK, unde p1, …, pK 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.

Cerinţă

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 doua numere pi ri, 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 <= 2000000000 (două miliarde)
• Şirul considerat este indexat începând de la 1.
• Se garantează că rezultatul va fi mai mic decât 10000000000 (zece miliarde). Programatorii în C++ pot folosi tipul de date long long, iar cei în Pascal tipul int64.

Exemple

resturi.inresturi.outExplicaţii
3 6 2 1 3 2 5 2 18 În acest caz, şirul considerat este: 0, 4, 6, 10, 16, 18, 24, …
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, …

autor: Tiberiu Dăneţ
propunător: Prof. Emanuela Cerchez
Liceul de Informatica ″Grigore Moisil″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la Lot AB 2004: comoara2, domino, frunze, grade, hof, jungla, sir6
De acelaşi autor: sub, albinuta, patrat, borg, matrice1
Despre divizibilitate: celule, cai, trei, ruleta, an, factori, perechi, anagrame, axa, perspic, scara, programs, iepuras2, fry, policefm, turist, kfactor, cuc, prime, sqr, evaluare, factk, div3, divizor, euclid, stop, matricea, mutare, viteza, ingerasi, prieteni, robinson, romeo, perechi1, sume1, fact, tzigla, cifru2, elfi, vraji, desen2, exponent, trapez, exp1, ron, spirala1, gardul, tort, poligon3, sume2, smith, biliard, printesa, secvente1, ultime4, padure, multiplu1, 235, iepurasi, numar3, cmmmc, randomizare, divizori, pitag, bileprime, pin, canguri, numar4, jocprim, covor, nivfractie, cmmdcsecv, ai, grupe2, numerus, sport2, fagure, grad2, sumdivprod, oak, sumprod, paisprezece, numere10, proddiv, puncte4, trifoi, cartier, alune, intersectii, divider, minm, numere11, prodnr, boltz, vistiernic, secvp, extraprime, divizori1, cumpanit, cntgcd, nrdiv, numere12, daruri, imprimanta, puteri, reflex, tg, sprime, diferenta, concurs4, vapoare, inventie, prime2
Despre secvenţe: degrade, hora, simetric, egal, ruleta, ecran, sirag, pasi, firma, br, numere2, termen, div, teatru, repeat, ratb, 2sec, sport, pikachu, suma3, panouri, sir5, mare, hof, efort, xor1, livada1, diff, popic, guess, albine1, permutare, miere, atelier, obstacole, echilibru1, lcdr, 3max, ksecv, maxbin, meteo1, galbeni, maxp, secvp, split, secvente2, ausoara, sminus, munte3, cool, betisoare, unudoi, charlie, lasere, arc, dominant, restaurare, roua
Despre căutare binară: gropi, pod, uscat, checkin, copaci, aven, br, furtuna, livada, numar, matrice, sume, bacan, toys, chimie2, trafic, ants, multiplu, ghici, sirag1, tabara, puncte1, centru, harta1, salvare, spion, poze, dist1, patrate5, lanterna, sea2, vot, standard, cantor, medalii, binperm, mobil, stalpi1, expo, miere, conferinta, subs, pack, obstacole, dag, acoperire, verigi, bradut2, triburi, intervale, mijloc, patru, eliminare, vectori1, calcule, secvp, dreapta, colina, ssk, robotics, cabana
Chestionare recomandate
surse trimise | ajutor