Fibonacci Again
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 31558 Accepted Submission(s): 15298
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.
Print the word "no" if not.
Sample Input
0
1
2
3
4
5
Sample Output
no
no
yes
no
no
no
原本想说打表fibonacci[n]，然后输入n，判断fibonacci[n]%3==0则输出yes否则no，竟然被WA，想不出原因，不过想想hdu也不会出这么简单的题，于是就研究了下
首先，fibonacci[n]=fibonacci[n-1]+fibonacci[n-2]，如果将fibonacci[n]用fibonacci[0]与fibonacci[1]表示的话，那就会得到下面的表达式
fibonacci[n]=f[n-2]*fibonacci[0]+f[n-1]*fibonacci[1]
其中f[n]为f[0]=1,f[1]=1的斐波那契数列，换句话说，不管起始数fibonacci[1,0]如何，它总能换成如上形式；
因此我们可以来研究看看这个最基本的斐波那契数组f[n]={ 1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 , 55.... }
设其中一个数为f[i],f[i] mod a = loop[i]
我没查过资料，就是有个猜想：loop[i]是一个循环数组
我编了个程序运算了下，f[i] mod 4 得到以 1,1,2,3,1,0,1 循环的数组，f[i] mod 3 得到以 1,1,2,0,2,2,1,0 循环的数组
f[i] mod 5 得到的比较长，但也是一个循环，这下算是有点底气了
既然是循环，就一定有共性
回到原题，既然f[i] mod 3 的循环只有8个元素，那就一个个试过去
其实正常的思路应该是这样，要让fibonacci[n] mod 3==0，就是要让[ f[n-2]*7 + f[n-1]*11 ] mod 3 == 0
即 ( f[n-2]+2f[n-1] ) mod 3 == 0;
即 ( loop[n-2]+2loop[n-1] ) mod 3 == 0;
这下就可以利用循环了
试过之后发现n==2 , 和 n==6 是可以的，之后又是循环，所以只要 n%8 == 2 或 n%8 == 6 就可以了
然后上面又等价于 n%4 == 2
就一步搞定啦
其实原本打表之后一个一个试，试过了发现2,6,10,14,18后面都是yes，所以~~~~你懂得，然后就AC了
做个总结：
一：
fibonacci[n]=f[n-2]*fibonacci[0]+f[n-1]*fibonacci[1]
其中f[n]为f[0]=1,f[1]=1的斐波那契数列，不管起始数fibonacci[1,0]如何，它总能换成如上形式；
二：
f[i] mod a = loop[i]
loop[i]是一个循环数组
三：
做到这种题首先一个一个试过去！！！！
贴上代码：
1 #include<iostream> 2 using namespace std; 3 int main() 4 { 5 int N; 6 while(cin>>N) 7 { 8 if ( (N+2)%4==0 ) 9 cout<<"yes "; 10 else 11 cout<<"no "; 12 } 13 }