Masala D
Antiqa funksiya
Quyida \(F(n)\) funksiyaning qiymatini hisoblash algoritmi berilgan. Bunda \(n\) natural son bo‘lib, quyidagi munosabatlar bilan berilgan:
- \(F(0)=0\);
- \(F(n)=F(n/2)\), agar \(n>0\) va juft son;
- \(F(n)=1+F(n−1)\), agar \(n\) toq son.
Savol: \(1≤n≤N\) oraliqda \(F(n)=K\) bo‘ladigan nechta son bor?
Kiruvchi ma'lumotlar:
N va K natural sonlar beriladi. \((1≤N≤10^{18})\), \((1≤K≤60)\)
Chiquvchi ma'lumotlar:
Masala javobini chop eting.
Misollar
| # | input.txt | output.txt |
|---|---|---|
| 1 |
3 10 2 73 3 15 7 |
5 24 0 |
Izoh:
1-testda
\(F(0)=0\)
\(F(1)=1+F(0)=1+0=1\)
\(F(2)=F(2/2)=F(1)=1\)
\(F(3)=1+F(3-1)=1+F(2)=1+1=2\) (To'g'ri keladi)
\(F(4)=F(4/2)=F(2)=1\)
\(F(5)=1+F(5-1)=1+F(4)=1+1=2\) (To'g'ri keladi)
\(F(6)=F(6/2)=F(3)=2\) (To'g'ri keladi)
\(F(7)=1+F(7-1)=1+F(6)=1+2=3\)
\(F(8)=F(8/4)=F(2)=1\)
\(F(9)=1+F(9-1)=1+F(8)=1+1=2 \)(To'g'ri keladi)
\(F(10)=F(10/2)=F(5)=2\) (To'g'ri keladi)
Demak 5 ta ekan.
Telegram kanalimizga obuna bo'ling