这题可以找规律也可以用矩阵乘法做。
矩阵解法：
f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7.
题意：给出一个递推公式，求第N项。
然后使用矩阵乘法时间复杂度为log（n）的一个算法。
代码：
#include<stdio.h>
struct M
{
int p[2][2] ; // 范围大的话用 long long
} ;
M mult(M a,M b)//矩阵相乘
{
int i,j,k ;
M c ;
for(i=0 ;i<2 ;i++)
for(j=0 ;j<2 ;j++)
{
c.p[i][j]=0 ;
for(k=0 ;k<2 ;k++)
{
c.p[i][j]=(c.p[i][j]+a.p[i][k]*b.p[k][j]%7)%7 ;
}
}
return c ;
}
M pow(M a,int k)//快速幂
{
M b={1,0,0,1} ; //相当于 ans=1 ；
while(k)
{
if(k&1)
b=mult(b,a) ;
a=mult(a,a) ;
k>>=1 ;
}
return b ;
}
int main()
{
int x,y,n ;
while(scanf("%d%d%d",&x,&y,&n)!=EOF)
{
if(!x&&!y&&!n)
break ;
M a={x,y,1,0} ; // M 相当于 int
M c=pow(a,n-2) ;
printf("%d\n",(c.p[0][0]+c.p[0][1])%7) ;
}
return 0 ;
}
找规律解法：
主要是找寻环节。
#include<stdio.h>
int f[52] ;
int main()
{
int i,j,a,b,n ;
f[1]=f[2]=1 ;
while(scanf("%d %d %d",&a,&b,&n),n)
{
for(i=3;i<52;i++)
f[i]=(a*f[i-1]+b*f[i-2])%7 ;
if(n<52) printf("%d\n",f[n]) ;
else
{
int g=0 ;
for(i=1;i<50;i++) // 找寻环节
{
for(j=i+1;j<51;j++)
if(f[i]==f[j]&&f[i+1]==f[j+1])
{
printf("%d\n",f[(n-i)%(j-i)+i]) ;
g=1 ;
break ;
}
if(g)
break ;
}
}
}
return 0;
}