HDOJ 1021 Fibonacci Again 【数论】

题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=1021

题目就是重新定义了一个斐波那契数列
给定数列的某一项如果该项的斐波那契数可以被3整除输出yes
否则输出no

1、【两个数的和】的【各位之和】 == 两个【数的各位之和】的【和】
2、能被3整除的数的【各位之和】也能被3整除
3、所以，得出公式 ( a + b ) % 3 = ( a % 3 + b % 3) % 3
然后预处理做个表就可以了

#include<iostream>
#include<cstdio>
using namespace std;
#define clr(c) memset(c, 0, sizeof(c));
const int INF = 0x3f3f3f3f;
typedef long long ll;
int n;
int fib[1000005];
void Pre(){
    fib[0] = 7 % 3;
    fib[1] = 11 % 3;
    for(int i = 2; i <= 1000000; i++){
        fib[i] = ((fib[i-1] % 3) + (fib[i-2] % 3)) % 3;
    }
}

int main(){
    Pre();
    while(~scanf("%d", &n)){
        if(fib[n]) puts("no");
        else puts("yes");
    }

    return 0;
}