《论取模的艺术》231760:菲波那契数列.递推ver

原题

错误代码：

#include<bits/stdc++.h>
using namespace std;

long long math(int a)
{
    if(a <= 2){
        return 1;
    }
    long long f0 = 1,f1 = 1,f2;
    for(int i = 3;i <= a;++ i){
        f2 = f1 + f0;
        f0 = f1;
        f1 = f2;
    }
    return f2;
}

int main()
{
    int n,a;
    scanf("%d",&n);
    for(int i = 1;i <= n;++ i){
        scanf("%d",&a);
        printf("%lld\n",math(a) % 1000);
    }
    return 0;    
}

当a大到2000左右的时候，long long也会爆掉，所以不能在结果处取模。
那么我们就在运算过程中取，也就是f2 = f1 + f0这个时候。对于加、减、除法运算来讲，运算过程中取模是无所谓的，这可以严谨的证明，

但我更愿意理解成 本质上就是结果要留的那几位在运算的数。

改进：

#include<bits/stdc++.h>
using namespace std;

int math(int a)
{
    if(a <= 2){
        return 1;
    }
    int f0 = 1,f1 = 1,f2;
    for(int i = 3;i <= a;++ i){
        f2 = (f1 + f0) % 1000;
        f0 = f1;
        f1 = f2;
    }
    return f2;
}

int main()
{
    int n,a;
    scanf("%d",&n);
    for(int i = 1;i <= n;++ i){
        scanf("%d",&a);
        printf("%d\n",math(a));
    }
    return 0;    
}

泪目。