Fişierul intrare/ieşire:leo.in, leo.outSursăIQ Academy
AutorCristian FrancuAdăugată defrancuCristian Francu francu
Timp execuţie pe test1.5 secLimită de memorie6144 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Leo (clasa a 6-a)

Leo este un pasionat al matematicii. Recent a întîlnit conceptul de numere abundente: sunt acele numere x a căror sumă a divizorilor proprii (divizori strict mai mici ca x) este strict mai mare decît x. De exemplu, 12 este un număr abundent deoarece divizorii lui sînt 1, 2, 3, 4 şi 6, iar suma lor este 16. Următoarele numere abundente sînt 18 şi 20.

"Ce numere interesante, oare le-aş putea găsi şi eu?" - s-a întrebat Leo. Îl puteţi ajuta?

Cerinţă

Leo vă va da un număr n între 3 şi 1000000. Voi va trebui să găsiţi:

  1. Cel mai mare număr xn cu proprietatea că reprezentarea lui în baza doi are fix o cifră 1.
  2. Cîte numere de la 1 la n sînt abundente.
  3. Cîte numere de la 1 la n au proprietatea că, reprezentate în baza doi, au acelaşi număr de cifre 1 ca reprezentarea în baza doi a sumei tuturor divizorilor lor (toţi divizorii, nu doar cei proprii).

Date de intrare

Fişierul de intrare leo.in conţine pe prima linie numărul cerinţei, 1, 2, sau 3. Pe a doua linie va conţine numărul n.

Date de ieşire

Pe prima linie a fişierului de ieşire leo.out veţi afişa astfel:

  • Dacă cerinţa este 1, cel mai mare număr xn cu proprietatea că reprezentarea lui în baza doi are fix o cifră 1. Numărul x va fi afişat în baza 10.
  • Dacă cerinţa este 2, numărul de numere abundente între 1 şi n, inclusiv 1 şi n.
  • Dacă cerinţa este 3, numărul de numere x între 1 şi n, inclusiv 1 şi n, ale căror sume ale tuturor divizorilor lor au acelaşi număr de cifre 1 în reprezentarea lor în baza doi ca şi reprezentarea în baza doi a numerelor x.

Restricţii

  • 3 ≤ n ≤ 1000000
  • suma tuturor divizorilor oricărui număr x nu va depăşi 5 milioane
  • Pentru rezolvarea primei cerinţe se acordă 20% din punctaj, pentru a doua cerinţă 30% din punctaj şi pentru a treia cerinţă 50% din punctaj.

Exemple

leo.inleo.outExplicaţie
1
16
16
Cel mai mare număr mai mic sau egal cu 16 care are o singură cifră 1 în reprezentarea în baza doi este chiar 16.
2
16
1
Avem un singur număr abundent, acela fiind 12, a cărui sumă a divizorilor stricţi este 1+2+3+4+6=16.
3
16
5
Avem 5 numere ale căror reprezentări în baza doi au acelaşi număr de cifre 1 ca şi suma divizorilor lor:
1(10) = 1(2), suma divizorilor este 1(10) = 1(2)
5(10) = 101(2), suma divizorilor este 1+5=6(10) = 110(2)
6(10) = 110(2), suma divizorilor este 1+2+3+6=12(10) = 1100(2)
10(10) = 1010(2), suma divizorilor este 1+2+5+10=18(10) = 10010(2)
13(10) = 1101(2), suma divizorilor este 1+13=14(10) = 1110(2)
1
20
16
Cel mai mare număr mai mic sau egal cu 20 care are o singură cifră 1 în reprezentarea în baza doi este 16.
2
20
3
Avem 3 numere abundente, 12, 18 şi 20.
3
20
6
Avem 6 numere ale căror reprezentări în baza doi au acelaşi număr de
cifre 1 ca şi suma divizorilor lor, 1, 5, 6, 10, 13, 17.
Trebuie sa te autentifici pentru a trimite solutii. Click aici