我们知道,每个非负十进制数可以用Fibonacci数的和来唯一表示(这里我们关注最小表示,即在数字的表示中没有连续的Fibonacci数,并且每个Fibonacci数最多只取一个在代表中).
例如:
1-> 1
2-> 10
3->100
4->101, here f1=1 , f2=2 and f(n)=f(n-1)+f(n-2);
所以每个十进制数可以在Fibonacci系统中表示为二进制序列.如果我们在Fibonacci系统中连续写出所有自然数,我们将获得如下序列:110100101 ...这称为"自然数的斐波那契位序列".
我的任务是计算第1位出现在该序列的前N位中的次数.由于N可以取1到10 ^ 15的值,我可以不存储斐波纳契数列吗？
例如:如果N是5,答案是3.