题目描述：
考点：模对加法没有影响
这里的考点很简单，难的是这道题目的大坑。
先贴代码：
ac代码：
#include <iostream>
using namespace std;
typedef long long ll;
const int N = 100010;
ll fib[N];
int main()
{
fib[1] = 1, fib[2] = 2;
for(int i = 3; i < N; i++)
fib[i] = (fib[i - 1] % 1000000 + fib[i - 2] % 1000000) % 1000000;
int n;
while(cin >> n)
{
if(n < 29) cout << fib[n] << endl;
else printf("%06d\n", fib[n]);
}
}
大坑在于你只能协程n < 29。而不能写成fib[n] / 1000000 == 0这种代码，可能会说，这样也能判断它是六位数啊。问题是，我们存fib的时候，已经取过模了，所有数都不可能超过六位数。
拿到这个29的方法就是我们在计算fib的时候，记录一下，如果这个数已经超过6位数了，也就是比一百万要大了，就记录一下。
因此可以写下面这个代码：
int x = 0;
for(int i = 3; i < N; i++)
{
fib[i] = fib[i - 1] + fib[i - 2];
if(fib[i] >= 1000000)
{
x = i;
break;
}
}
for(int i = x; i < N; i++)
{
fib[i] = (fib[i - 1] + fib[i - 2]) % 1000000;
}
还有一点：取模的时候会把最前面的0给删掉，因此最后要补前导0
