hdoj1021 Fibonacci Again

题目：

Problem Description
There are another kind of Fibonacci numbers: F(0) = 7, F(1) = 11, F(n) = F(n-1) + F(n-2) (n>=2).
Input
Input consists of a sequence of lines, each containing an integer n. (n < 1,000,000).
Output
Print the word "yes" if 3 divide evenly into F(n).
Print the word "no" if not.
Sample Input
0
1
2
3
4
5
Sample Output
no
no
yes
no
no
no

此题与斐波拉契数列有点相似，但是如果是一个一个求出来打表再判断它是否被3整除，肯定会出错（因为此题n的值可能很大，求出来的值可能会爆long long）。但此题可以每次对结果模3，这样就可以了。

参考代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
const int N = 1000000+5;
typedef long long ll;
using namespace std;
ll num[N];
void dabiao() {
    num[0] = 7 % 3;
    num[1] = 11 % 3;
    for (int i = 2;i <= 1000000;++i) {
        num[i] = (num[i-1] + num[i-2]) % 3;
    }
}
int main() {
    dabiao();
    int n;
    while (scanf("%d", &n) != EOF) {
        if (num[n] == 0) printf("yes\n");
        else printf("no\n");
    }
    return 0;
}

另外，我在网上看到了一种找规律的方法，可以不打表。
我们可以先算出前面多组数据的值，然后就可以发现规律：
每8个数据一组，结果我们发现：
根据公式求出来的结果模3的余数是：1 2 0 2 2 1 0 1.
这八个数字模8的结果是：0 1 2 3 4 5 6 7 8.

规律：给定的数模8的结果只要是2或6，根据公式求出来的数就一定能被3整除。

参考代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
void judge(int num) {
    num = num % 8;
    if (num == 2 || num == 6) {
        printf("yes\n");
    }
    else {
        printf("no\n");
    }
}
int main() {
    int num;
    while (scanf("%d", &num) != EOF) {
        judge(num);
    }
    return 0;
}