Fişierul intrare/ieşire:bonus.in, bonus.outSursăRMI 2016
AutorCristian FrancuAdăugată defrancuCristian Francu francu
Timp execuţie pe test1 secLimită de memorie512 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

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 ≤ iN

Exemplu

bonus.inbonus.outExplicaţ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ă.
Trebuie sa te autentifici pentru a trimite solutii. Click aici