Java如何编写Fibonacci数列取余的示例代码？

本文共计660个文字，预计阅读时间需要3分钟。

描述：斐波那契数列的递推公式为：Fn=Fn-1 + Fn-2，其中F1=F2=1。当n比较大时，Fn也非常大。现在我们想知道，Fn除以10007的余数是多少。

输入：多组测试数据，每组数据包含一个整数n（1 <=n <=1000000）。

Description
Fibonacci数列的递推公式为：Fn=Fn-1+Fn-2，其中F1=F2=1。

当n比较大时，Fn也非常大，现在我们想知道，Fn除以10007的余数是多少。

Input
多组测试数据

输入包含一个整数n。1 <= n <= 1,000,000。

Output
每组输出一行，包含一个整数，表示Fn除以10007的余数。

Sample Input
10
22

Sample Output
55
7704

利用余数三大定理：

1.余数的加法定理

a与b的和除以c的余数，等于a,b分别除以c的余数之和，或这个和除以c的余数。