Revizia anterioară Revizia următoare
| Fișierul intrare/ieșire | john.in, john.out | Sursă | IQ Academy |
|---|---|---|---|
| Autor | Cristian Frâncu | Adăugată de |
Cristian Frâncu
•
francu
|
| Timp de execuție pe test | 0.4 sec | Limită de memorie | 6144 KB |
| Scorul tău | N/A | Dificultate |
  2.75
|
Poți vedea testele pentru această problemă accesând
atașamentele
.
Vezi soluțiile trimise | Statistici
John (clasa a 6-a)
John vrea să îi facă un cadou special de Crăciun Alexandrei (Alexandra fiind bună matematiciană). Citind o poveste el a aflat că în evul mediu îndrăgostiții sculptau pe două fructe numere prietene, iar apoi fiecare mînca unul din fructe. Căutînd despre numerele prietene, a găsit că au remarcabila proprietate că fiecare din ele este suma divizorilor proprii ai celuilalt număr (divizorii proprii ai lui x sînt acei divizori strict mai mici ca x).
De exemplu, numerele 220, 284 sînt prietene, deoarece divizorii proprii ai lui 220 sînt 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 și 110, a căror sumă este 284, iar divizorii proprii ai lui 284 sînt 1, 2, 4, 71 și 142, a căror sumă este 220.
John vrea să îi facă cadou Alexandrei un suport pentru vase fierbinți care să aibă gravat pe fiecare parte cîte un număr, iar numerele să fie prietene. Îl puteți ajuta?
Cerință
John vă dă un număr n între 3 și 1000000 și vă roagă să calculați:
- Cel mai mare număr z ≤ n cu proprietatea că reprezentarea lui în baza doi are fix două cifre 1.
- Cîte perechi de numere mai mici sau egale cu n sînt prietene (ordinea numerelor în pereche nu contează).
- Cîte numere între 1 și n au proprietatea că suma divizorilor lor proprii, reprezentată în baza doi, este un număr palindrom.
Date de intrare
Fișierul de intrare john.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 john.out veți afișa astfel:
- Dacă cerința este 1, cel mai mare număr z ≤ n cu proprietatea că reprezentarea lui în baza doi are fix două cifre 1. Numărul z va fi afișat în baza 10.
- Dacă cerința este 2, numărul de perechi de numere prietene între 1 și n.
- Dacă cerința este 3, numărul de numere a căror sumă a divizorilor proprii este palindrom în baza doi.
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.
Exemplu
| john.in | john.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. |
