神奇的数列

转载自 ：https://zhuanlan.zhihu.com/p/159238355

首先，我们可以看x在数列的3个位置上出现了多少次，然后再看x在数列4,5......位置上出现了多少次。

现在问题变成了如何确定在位置start上出现了多少次呢？

想解决这个问题，需要找到斐波那契数列的规律，假设第一个数是a，第二数是b，那么这个数列可以描述成：

a, b, a+b, a+2b, 2a+3b, 3a+5b, 5a+8b, 8a+13b .....

a 的系数为:1,0,1,1,2,3,5,8,b的系数为 :0,1,1,2,3,5,8。 可以发现a和b的系数都是斐波那契数列。当start-1位置上a的系数为i ,b的的系数为j时，start位置上a的系数为j， b的的系数为i+j。

确定完位置start上，a的系数为i，b的系数为j后，我们只用计算有多少种a，b的组合使得a*i+b*j=x，就可以得到x在位置start上出现了多少次。

假设有两组 都满足 ， ， 两公式相减可以得到： （这里假设 ，那么 ）。由于斐波那契数列中的数是互斥的，那么我们可以知道 。

即在位置start上，有 种a，b的组合使得a*i+b*j=x。

最后代码如下：

import sys
import math
x = int(sys.stdin.readline().strip('\n').strip())

i,j=1,1
start=3
while True:
    p=1
    while (x-i*p)%j!=0 and i*p<x:
        p+=1
    if i*p>=x:
        break
    print('{0} {1}'.format(start,math.ceil((x-i*p)*1.0/(i*j))))
    i,j=j,i+j