C语言 斐波那切数列 每行输出F(n)%m
这个是最正宗的斐波那切数列.F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2) (n>=2)
每行输入一个数n和m（n <= 2*10^9 ,m < 10^4)
每行输出F(n)%m.
Sample Input
1 3
2 4
3 5
4 6
Sample Output
1
1
2
3
有什么简单的C语言方法去做吗
[解决办法]
循环就行了。
[解决办法]
n <= 2*10^9。需要用矩阵乘法。[1,1;1,0]*[F[n];F[n-1]]=[F[n+1];F[n]]。所以如果令A矩阵是[1,1;1,0]，则[F[n];F[n-1]]=A^(n-1)*[1;0]。用log(n)的复杂度算出A^(n-1)以后F[n]就出来了。当然所有运算都是mod m进行。
