试题 算法提高 研究兔子的土豪
资源限制
时间限制：1.0s 内存限制：256.0MB
问题描述
某天，HWD老师开始研究兔子，因为他是个土豪
，所以他居然一下子买了一个可以容纳10^18代兔子的巨大笼子（好像比我们伟大的地球母亲大一点点？），并开始研究它们，之后，他了解了兔子的繁衍规律：即fibonacci数列。
兔子繁殖了n代后，HWD老师很开心。
但是，HWD老师有密集恐惧症，所以，他只能去卖了兔子，他找到了一个好的雇主，但是这个雇主有强迫症，他只每次收购1007只兔子，HWD老师为了避免自己的密集恐惧症，要尽量多的卖了兔子。
但是即便是密集恐惧症，也打击不了HWD老师研究兔子的决心，他数着数着自己剩下的兔子……
输入格式
HWD老师让兔子繁衍了几代（一个整数，没有其他字符）。
输出格式
HWD老师剩余（残余？）的兔子（一个整数，忽略行尾回车及空格）。
样例输入
1
样例输出
1
数据规模和约定
兔子的总量最大时小于HWD老师笼子的大小。
f[1]=1，f[2]=1，f[3]=2 ……
PS：
斐波那契有一定的循环， 这里直接偷个懒，链接地址
对于斐波那契数列a[n]对m取模。
由于斐波那契数列的特征，只要存在a[j] mod m = a[k] mod m且a[j+1] mod m = a[k+1] mod m (j<k)，则a[j] ~ a[k-1]为循环节。
考虑两两相邻的斐波那契数 mod m的数对，最多只有m * (m - 1)种可能。
根据抽屉原理，a[0]~a[m * (m - 1) + 1]中必然存在相邻数对存在重复。
(●ˇ∀ˇ●)（可以手动找一下，小编直接百度了）
实在不行，自己求斐波那契数列的循环节
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long n = sc.nextLong();
if (n == 1 || n == 2) {
System.out.print(1);
return;
}
int mod = 1007;
long a = -1;
long b = -1;
n %= 108;
for (int i = 1; i <= n; i++) {
if (i == 1) {
a = 1;
continue;
} else if (i == 2) {
b = 1;
continue;
}
long c = (a + b) % mod;
a = b;
b = c;
}
System.out.print(b);
}
}