hdu 1021 Fibonacci Again(矩阵连乘 || 循环节)

hdu 1021 Fibonacci Again(矩阵连乘 || 循环节)

题目：​​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

矩阵连乘：

#include #include using namespace std;struct matrie{ int m[2][2];};matrie A={ // f[n],f[n-1] ~ f[1],f[0] ~ pow=n-1 1,1, 1,0};matrie I={ 1,0, 0,1};matrie multi(matrie a,matrie b){ matrie c; for(int i=0;i<2;i++){ for(int j=0;j<2;j++){ c.m[i][j]=0; for(int k=0;k<2;k++){ c.m[i][j]+=(a.m[i][k]*b.m[k][j])%3; } c.m[i][j]%=3; } } return c;}matrie power(int p){ matrie ans=I,tmp=A; // 矩阵结构体可以直接相等 while(p){ if(p&1) ans=multi(ans,tmp); tmp=multi(tmp,tmp); p>>=1; } return ans;}int main(){ //freopen("cin.txt","r",stdin); int n; while(cin>>n){ if(n==0){ puts("no"); continue; } matrie w=power(n-1); int ans=(w.m[0][0]*7+w.m[0][1]*11)%3; if(ans==0)puts("yes"); else puts("no"); } return 0;}

循环节：

#include #include using namespace std;typedef long long LL;LL f[100];int main(){ /*f[0]=7; f[1]=11; for(int i=2;i<40;i++){ f[i]=(f[i-1]+f[i-2])%3; cout<>n){ if((n-2)%4==0)printf("yes\n"); else puts("no"); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。