| 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 | 1.5 sec | Limită de memorie | 6144 KB |
| Scorul tău | N/A | Dificultate |
  3
|
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ă ele sînt două numere distincte cu 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, inclusiv 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, inclusiv 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 22 |
20 |
Cel mai mare număr mai mic sau egal cu 22 care are exact două cifre 1 în reprezentarea în baza doi este 20. deoarece 20(10)=10100(2), iar următorul număr ar fi 11000(2)=24(10), care ar fi prea mare. |
| 2 284 |
1 |
Avem o singură pereche de numere prietene mai mici sau egale cu 284, anume 220 și 284. |
| 3 15 |
10 |
Avem 10 numere mai mici sau egale cu 15 a căror sumă a divizorilor proprii are reprezentarea în baza doi palindrom: 1, suma divizorilor este 0(10) = 0(2) 2, suma divizorilor este 1(10) = 1(2) 3, suma divizorilor este 1(10) = 1(2) 4, suma divizorilor este 1+2=3(10) = 11(2) 5, suma divizorilor este 1(10) = 1(2) 7, suma divizorilor este 1(10) = 1(2) 8, suma divizorilor este 1+2+4=7(10) = 111(2) 11, suma divizorilor este 1(10) = 1(2) 13, suma divizorilor este 1(10) = 1(2) 15, suma divizorilor este 1+3+5=9(10) = 1001(2) |
| 1 30 |
24 |
Cel mai mare număr mai mic sau egal cu 30 care are exact două cifre 1 în reprezentarea în baza doi este 24. |
| 2 2000 |
2 |
Avem două perechi de numere prietene mai mici sau egale cu 2000, anume 220, 284 și 1184, 1210. |
| 3 20 |
14 |
Avem 14 numere mai mici sau egale cu 20 a căror sumă a divizorilor proprii are reprezentarea în baza doi palindrom. |
