Kvadrati

Osnovne informacije

Omejitve
  • Čas: 2 s
  • Spomin: 128 MB
Avtor:
  • Vid Kocijan
  • UPM 2019

Pošlji rešitev



Tvoji rezultati.
Nisi poslal še nobene rešitve.
Več »

Dano je naravno število n<2^{63}. Na koliko načinov lahko premešamo njegove bite v dvojiškem zapisu, da dobimo popoln kvadrat? Veljajo le zapisi, ki nimajo vodilnih ničel.

Vhodni podatki

Na vhodu se nahaja zgolj naravno število n.

Omejitve vhodnih podatkov

  • 1 \leq n < 2^{63}

Izhodni podatki

Izpišite eno samo število — na koliko načinov lahko premešamo bite števila n v dvojiškem zapisu, da dobimo popoln kvadrat brez vodilnih ničel.

Primeri

Vhod

4

Izhod

1

Vhod

1810

Izhod

4

Vhod

524799

Izhod

47

Komentar

Pri drugem primeru imamo n = 1810. Dvojiški zapis tega števila je 11100010010. Z mešanjem bitov lahko dobimo naslednje popolne kvadrate: 1225, 1444, 1681 in 1936. Njihovi dvojiški zapisi po vrsti so: 10011001001, 10110100100, 11010010001 in 11110010000.

Tip: Log in to
  • submit and test your solution
  • post or read questions and answers about this task