Fibonacci Again

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

Total Submission(s): 37229    Accepted Submission(s): 17970

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

 

 算法分析：

      一开始用的__int64 开数组挂了，估计也会挂，n的范围可以大到1000000， 如果n的值比较大，那么f[n] 就超数据类型了。

      查到了这个公式：

                           （m+n）%3 = (m%3+n%3)%3 ;

                           取完余数后再存到数组里，f[n]就不会超数据类型了。

                 

#include 
       
        #include 
        
         #include 
         
          int f[1000001];int main(){    int n;	int i, j;    f[0]=7%3 ;	f[1]=11%3 ;	for(i=2; i<1000000; i++)	{		f[i]=(f[i-1]%3+f[i-2]%3)%3;	}	while(scanf("%d", &n)!=EOF)	{		if(f[n]==0)			printf("yes\n");		else			printf("no\n");	}	return 0;}