Fibonacci Again（数学）

Fibonacci Again

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 34337    Accepted Submission(s): 16585

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

 

     题意：

     斐波那契数为 F [ 0 ] = 7，F [ 1 ] = 11，F [ N ] = F [ N - 1 ] + F [ N - 2 ] ( N >= 2 )，输入 N（<= 1000000），问 F[ N ] 能否被 3 整除。

 

     思路：

     数学。先把结果保存起来再判能不能整除的话，以 N == 1000000 的话 long long 都会爆，所以边加就边求余数，直接数组保存余数结果就好，若为 0 则输出 yes，否则则为 no。

     还有一种方法，找规律，按数组的顺序，余数的结果为 1,2,0,2,2,1,0,1,1,2,0,2,2,1,0……可以发现，当下标（n - 2）能整除 4 的时候能整除3，所以可以通过这个方法直接输出 yes 还是 no。

 

     AC：

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int MAX = 1000005;

int num[MAX];

void solve() {
        num[0] = 1;
        num[1] = 2;
        for (int i = 2; i < MAX; ++i)
                num[i] = (num[i - 1] + num[i - 2]) % 3;
}

int main () {
        int n;
        solve();
        while (~scanf("%d", &n)) {
                if (num[n]) printf("no\n");
                else printf("yes\n");
        }
        return 0;
}

 

    or：

#include <cstdio>

using namespace std;

int main () {
        int n;
        while (~scanf("%d", &n)) {
                (n - 2) % 4 ? printf("no\n") : printf("yes\n");
        }
        return 0;
}