Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

　　　　　　　　　　　Total Submission(s): 68704    Accepted Submission(s): 31604

 

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)    童鞋们应该很快就想到了题目中的 Fibonacci

然而水平非常low的我只会写递归，so 。。MLE       then我发现 n % 4 == 2 输出“yes”，否则输出“no”

然后我去找了参加省选的学姐（dalao一枚），she said :"你用dfs当然会MLE了，你改成用递推，你递推会写吗？"

然后我告诉了她我找的规律，然后学姐默默地找到了另一个规律：1 2 0 2 2 1 0 1 1 2 0 2 2 1 0 1 ......

但是我还是按我自己的写了（比较lan）

所以一共有三种写法

#include
        
         #include
         
          using namespace std;int n;int f[1000005];int dfs(int x) {    if(f[x] != 0) return f[x];    f[x] = dfs(x-1) + dfs(x-2);}int main() {    f[0] = 7; f[1] = 11;    while(scanf("%d", &n) != EOF) {        int t = dfs(n);        if(t%3 == 0) printf("yes\n");        else printf("no\n");    }    return 0;}
         
        

#include
        
         using namespace std;int n;void judge(int x) {    if(x%4 == 2) printf("yes\n");    else printf("no\n"); }int main() {    while(scanf("%d", &n) != EOF) {        judge(n);    }    return 0;}
        

其他你们就自己写吧  嗯