Fișierul intrare/ieșire leo.in, leo.out Sursă IQ Academy
Autor Cristian Frâncu Adăugată de avatar francu Cristian Frâncu francu
Timp de execuție pe test 1.5 sec Limită de memorie 6144 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

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:

  1. Cel mai mare număr xn cu proprietatea că reprezentarea lui în baza doi are fix o cifră 1.
  2. Cîte numere de la 1 la n sînt abundente.
  3. 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 xn 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.

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 4 categorii