Fişierul intrare/ieşire: | bonus.in, bonus.out | Sursă | RMI 2016 |
Autor | Cristian Francu | Adăugată de | |
Timp execuţie pe test | 1 sec | Limită de memorie | 512 kbytes |
Scorul tău | N/A | Dificultate |
Bonus galactic (clasele 11-12)
Parlamentul Federaţiei Galactice, în scădere de popularitate, a hotarît să mai arunce un os fiinţelor inteligente din galaxie. Mai exact, a hotărît să dea o primă tuturor galaxienilor care împlinesc o sumă rotundă de ani. Propunerea de lege a fost atacată însă de diverşi oportunişti, pe motivul că sistemele solare au ani de lungime diferită. După un an de parlamentări federaţia a decis să ia în considerare vîrsta în Ani Galactici Standard, ceea ce a dus la un val de nemulţumiri din partea celor ce nu se descurcau cu conversiile, căci picasera bacul galactic. Aşa încît ei au atacat din nou legea, pe motiv că fiecare specie foloseşte propria bază de numeraţie, deci nu se poate defini un număr rotund. Dupa încă un an de deliberări parlamentarii au decis că un număr de ani N va fi considerat rotund dacă el se poate scrie sub forma 100...100...0 într-o bază oarecare B (exact două cifre 1, şi zero sau mai multe cifre 0).
Cîrcotasii nemaiavînd ce spune, legea a fost trecută şi a apărut impasul: numărul de cetăţeni galactici fiind foarte mare, parlamentarii nu ştiu să calculeze care vîrste sînt rotunde şi care nu, suficient de repede ca cetăţenii să primească primele înainte de obştescul lor sfîrşit.
Cerinţă
Parlamentul vă roagă pe voi să îl ajutaţi. Vîrstele cetăţenilor variază între 3 şi 264-1 ani, iar numărul aproximat al cetăţenilor galactici este între 1 şi 100 000. Dîndu-se numărul N al cetăţenilor precum şi fiecare vîrstă Xi, voi trebuie să calculaţi pentru fiecare Xi baza minimă în care ea este număr rotund. Dacă nu exista nici o bază, veţi afişa 0.
Date de intrare
Fişierul de intrare bonus.in conţine pe prima linie numărul N, reprezentînd numărul de cetăţeni ai galaxiei. Următoarele N linii conţin întregii X1, X2, ..., XN, cîte unul pe linie.
Date de ieşire
Fişierul de ieşire bonus.out va conţine N linii. Linia i va conţine un singur număr, cea mai mică bază în care Xi este număr rotund, sau zero dacă acea bază nu există.
Restricţii
- 1 ≤ N ≤ 100,000
- pentru 20% din teste 1 ≤ N ≤ 10,000
- 3 ≤ Xi ≤ 264-1 pentru orice 1 ≤ i ≤ N
Exemplu
bonus.in | bonus.out | Explicaţie |
---|---|---|
5 36 26 80 56 125 | 2 5 2 7 124 | 36 = 1001002 26 = 1015 80 = 10100002 56 = 1107 125 = 11124 Unele numere sînt rotunde în multiple baze. De exemplu 36 este rotund şi în baza 3: 36 = 11003. Însă răspunsul trebuie să fie baza cea mai mică. |