Question

杭电acm 1005（不是超时就是wa求高手赐教）!

一下是我的代码：
#include<stdio.h>
int main()
{
int A=0,B=0,n=0;
int f[101]={0};
f[1]=1;
f[2]=1;
while(scanf("%d %d %d",&A,&B,&n)&&(A||B||n))
{
int m=3;
int k=3;
int i=1,j=3;
int move;
int sd=0;
f[1]=1;
f[2]=1;
f[m]=(A*f[(m-1)]+B*f[(m-2)])%7;
while(m<=100)
{
f[m]=(A*f[(m-1)]+B*f[(m-2)])%7;
m++;
}
while(1)
{ move=i;
while(move<j)
{ if((j+move-i)>1000)
break;
if(f[move]!=f[j+move-i])
break;
move++;

}
if(move==j)
{ move=move-1;
break;
}
else
j++;
if(j>1000)
break;//不加此句显示超时
}
sd=n%move;
if(sd!=0)
printf("%d\n",f[sd]);
if(sd==0)
printf("%d\n",f[move]);//最终结果wa，郁闷
}
return 0;
}

Answer 1

这道题其实就是把周期找出来就ok了
#include <stdio.h>
int main()
{
int s[52],a,b,i,n,t;
s[1]=1;
s[2]=1;
while((scanf("%d %d %d",&a,&b,&n)!=EOF),a+b+n!=0)
{
a=a%7;
b=b%7;
for(i=3;i<52;i++)
s[i]=(a*s[i-1]+b*s[i-2])%7; //将所以可能的结果保存在数组s里面
for(i=3;i<52;i++)
if(s[i]==s[1]&&s[i+1]==s[2]) //找周期
break;
t=i-1; //周期为t
if(n%t==0)
printf("%d\n",s[t]);
else
printf("%d\n",s[n%t]);
}
return(0);
}

追问

我当然知道找周期，关键是我的拿错了？

追答

求周期的时候你想的复杂了，反而很容易出错，只要飞f[1]==f[T+1]&&f[2]==f[T+2]就ok了
给你改了一下代码：自己在想想。。
while(1)
{
move=i;
while(move1000)
break;
if(f[move]!=f[j+move-i])
break;
move++;
if(move>2) //这里只要有两次相等就行了，即：f[1]=f[j-i+1]与f[2]=f[j-i+2]
break;

}
if(move>2) //move>2，由上面可以知道周期就求出来了，但是周期为j-i
break;
else
j++;
if(j>1000)
break;
}
sd=n%(j-i); //周期为j-i
if(sd!=0)
printf("%d\n",f[sd]);
if(sd==0)
printf("%d\n",f[j-i]);