Fişierul intrare/ieşire: | leo.in, leo.out | Sursă | IQ Academy |
Autor | Cristian Francu | Adăugată de | |
Timp execuţie pe test | 1.5 sec | Limită de memorie | 6144 kbytes |
Scorul tău | N/A | Dificultate |
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:
- Cel mai mare număr x ≤ n cu proprietatea că reprezentarea lui în baza doi are fix o cifră 1.
- Cîte numere de la 1 la n sînt abundente.
- 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 x ≤ n 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.in | leo.out | Explicaţ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. |