学步园

http://acm.hdu.edu.cn/showproblem.php?pid=1005

f[1]=1,f[2]=1,f[n]=(A*f[n-1]+B*f[n-2])%7  (1 <= A, B <= 1000, 1 <= n <= 100,000,000).

n这么大,暴力是肯定TLE了.

1。由题目的式子可知0<=f[n]<=6,

2。而每个f[n]又是由(f[n-1],f[n-2])这个组合通过计算得出来的,

由以上两点可以推出,(f[n-1],f[n-2])出现重复的组合的最大周期为7*7=49, 即f[n]的最大周期

所有, 我们只要算出一个周期中所有的f[n]的值并记录下周期i即可.

#include<stdio.h><br /> int main()<br /> {<br /> int a,b,n,i,f[53];<br /> while(scanf("%d%d%d",&a,&b,&n)!=EOF)<br /> {<br /> if(a==0 && b==0 && n==0)<br /> break;<br /> if(n==1 || n==2)<br /> {<br /> puts("1");<br /> continue;<br /> }<br /> f[1]=1,f[2]=1;<br /> a%=7,b%=7;<br /> for(i=3;i<=52;i++)<br /> {<br /> f[i]=(a*f[i-1]+b*f[i-2])%7;<br /> if(f[i-1]==1 && f[i]==1)<br /> break;<br /> }<br /> i-=2;<br /> n%=i;<br /> f[0]=f[i];<br /> printf("%d/n",f[n]);<br /> }<br /> return 0;<br /> }