题目链接
题目描述: 考点:模对加法没有影响
这里的考点很简单,难的是这道题目的大坑。 先贴代码:
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
|