1022. Fib数列

Description

定义Fib数列： $1, 1, 2, 3, 5, 8, 13, \dots$

求第 $N$

项除以 $2010$

的余数

Input Format

输入仅一行，为一个整数 $N$

Output Format

输出仅一行，为第 $N$

$2010$

的余数

Sample Input

Sample Output

Limits:

对于70%的数据 $N \leq 1, 000, 000$

对于100%的数据 $N \leq 210, 000, 000, 000$

 

#include<iostream>
using namespace std;

int main(){
    int t;
    long long n;
    cin>>n;
    int a=1,b=1;
    if(n==1 || n==2){
        cout<<"1";
    }else{
        for(long long i=3;i<=n;i++){
            t=a+b;
            if(t>2010){
                t-=2010;
            }
            a=b;
            b=t;
        }
        cout<<t;
    }
    return 0;
}

$N \leq 210, 000, 000, 000$