HDOJ-1021

Fibonacci Again

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

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

本题数据较大，故不适合用递推来解决，既然不能递推，我们很自然的就会想到找规律。

根据题目已知条件：
Print the word”yes” if 3 divide evenly into F(n)；Print the word”no” if not.
这里mod取值为3，则可将公式条件演变为：
综上所述，可得到以下对应关系：F(0)= 1, F(1) = 2, F(n) = ( F(n-1) + F(n-2) )( mod 3) (n>=2).
index　　0　　1　　2　　3　　4　　5　　6　　7　　8　　9　　10　　11　　12　　13
value　　1　　2　　0　　2　　2　　1　　0　　1　　1　　2　　 0　　　2　　　2　　1
print　　no　no　yes　no　　no　no　yes　 no　 no　 no　　yes　　no　　no　　no
这样我们就得到了如下规律：从第2个开始每隔4个循环一次。

附AC代码：

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 using namespace std;
 5 int main(){
 6     int n;
 7     while(~scanf("%d",&n)){
 8         if((n-2)%4)
 9         printf("no
");
10         else
11         printf("yes
");
12     }
13     return 0;
14 }