Fişierul intrare/ieşire:john.in, john.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

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:

  1. Cel mai mare număr zn cu proprietatea că reprezentarea lui în baza doi are fix două cifre 1.
  2. Cîte perechi de numere mai mici sau egale cu n sînt prietene (ordinea numerelor în pereche nu contează).
  3. 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 zn 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.injohn.outExplicaţ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.
Trebuie sa te autentifici pentru a trimite solutii. Click aici