Question

杭电acm1005超时

#include<stdio.h>
void main()
{
int a,b,n,m,t;
int d[50]={0,1,1};

while(scanf("%d %d %d",&a,&b,&n))
{
if(a==0&&b==0&&n==0)
break;
if(n>=3)
{
for(m=3;m<50&&m<=n;m++)
{
d[m]=(a*d[m-1]+b*d[m-2])%7;
if(d[m]==1&&d[m-1]==1)
{t=m-2;break;}
}
n=n%t;
if(n==0)
n=t;
}
printf("%d\n%d\n",t,d[n]);
}
}
帮忙改下

Answer 1

周期的。
// 下面是我的AC代码
#include <stdio.h>
int main()
{
int a,b,n;
int f[201];
int i;
scanf("%d %d %d",&a,&b,&n);
while (a!=0||b!=0||n!=0)
{
f[1]=1;
f[2]=1;
if (n>=3)
{
for(i=3;i<200;i++)
{
f[i]=(a*f[i-1]+b*f[i-2])%7;
if ((f[i-1]==1)&&(f[i]==1))
{
break;
}
}
i=i-2;
n=n%i;
if (n==0)
{
n=i;
}
printf("%d\n",f[n]);
}
else
{
printf("1\n");
}
scanf("%d %d %d",&a,&b,&n);
}
return 0;
}

Answer 2

这是我自己写的代码：AC了，供大家参考！

#include <cstdlib>
#include <iostream>

using namespace std;

int A[10000];

int main(int argc, char *argv[])
{
int a,b,n,k1,k2,k3,i,j,M,N;
A[1]=A[2]=1;
while(cin>>a>>b>>n&&a&&b&&n)
{
M=0;
N=-1;
k1=k2=1;
for(i=3;i<=n;i++)
{
k3=(a*k2+b*k1)%7;
k1=k2;
k2=k3;
A[i]=k3;
if(N==-1)
{
for(j=1;j<i-2;j++)
{
if(k1==A[j]&&k2==A[j+1]){N=j;break;}//从j开始循环
}
}
else
{
M=i-N-2;
break;
}
}
if(N==-1||n<N)cout<<A[n]<<endl;
else
{
n-=(N-1);
n%=M;
if(n==0)n=M;
cout<<A[n+N-1]<<endl;
}
}
system("PAUSE");
return 0;
}

Answer 3

你这个输出有问题， printf("%d\n%d\n",t,d[n]);只要求输出一个
、
#include<stdio.h>
int main()
{
int a,b,n,m,t;
int d[50]={0,1,1};

while(scanf("%d %d %d",&a,&b,&n))
{
if(a==0&&b==0&&n==0)
break;
if(n>=3)
{
for(m=3;m<50&&m<=n;m++)
{
d[m]=((a*d[m-1])%7+(b*d[m-2])%7)%7;
if(d[m]==1&&d[m-1]==1)
{t=m-2;break;}
}
n=n%t;
if(n==0)
n=t;
}
printf("%d\n",t,d[n]);
}
return 0;
}
我改成这样是wa，我你这个方法没问题，我看你的这个周期找的不对。
下面这个是我ac的代码，你参考一下吧
#include <iostream>
using namespace std;
int f[50];
int main()
{
int a,b,n;
int flag=0;
f[0]=f[1]=1;
while(cin>>a>>b>>n)
{
if(!a||!b||!n)break;
int i,start,t,j;
flag=0;
for(i=2;i<50;i++)
{
f[i]=(a*f[i-1]%7+b*f[i-2]%7)%7;
for(j=i-1;j>=0;j--)
if(f[j]==f[i]&&f[j-1]==f[i-1])
{ t=i-j;start=j-1;flag=1;break; }
}
if(n==1||n==2)
printf("1\n");
else
printf("%d\n",f[start+(n-1)%t]);
}

}

Answer 4

贪心 不能暴力的