| Program | |
Nekatere funkcije najlažje opišemo rekurzivno. Taka je tudi naša
enoparametricna družina. Funkcije iz te družine slikajo iz pozitivnih
celih števil v pozitivna cela števila. Baza rekurzije je predpis F(1)=a.
Pri rekurzivnem pravilu locimo dve možnosti. Ce je argument sod, potem
velja F(2n)=F(n). Ce pa je argument lih, potem imamo F(2n+1)=F(n)+F(n+1).
Vaša naloga je napisati program, ki bo dovolj hitro racunal vrednosti funkcije
F.
Vsaka vrstica vhodne datoteke vsebuje dve števili: n in a. Število n je med 1 in 2000000000, število a pa med 1 in 10000. Izracunati je treba vrednost F(n) pri pogoju F(1)=a. Zadnja vrstica datoteke vsebuje samo število 0. Testna datoteka ne bo vsebovala vec kot 1000 vrstic.
Vsaka vrstica izhodne datoteke naj vsebuje ustrezno vrednost F(n), ce je ta
manjša ali enaka 1000000000, ali pa besedico overflow, kadar
je rezultat vecji od milijarde. Izpis naj ne vsebuje odvecnih presledkov.
Primer vhodnih podatkov
13 2
1431655765 1
22369621 9999
0
Pricakovan izpis
10
2178309
overflow