Fișierul intrare/ieșire | leo.in, leo.out | Sursă | IQ Academy |
---|---|---|---|
Autor | Cristian Frâncu | Adăugată de | Cristian Frâncu • francu |
Timp de execuție pe test | 1.5 sec | Limită de memorie | 6144 KB |
Scorul tău | N/A | Dificultate |
Vezi soluțiile trimise | Statistici
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. |