Question

杭电acm1005 WA 求改

#include<stdio.h>
#include<string.h>
int main()
{
freopen("1.txt","r",stdin);
int a[101];
int mark[7][7];
int A,B,n,cycle,i;
a[1]=a[2]=1;
a[0]=0;
while(1)
{
scanf("%d%d%d",&A,&B,&n);
if(A==0&&B==0&&n==0)
break;
memset(mark,0,sizeof(mark));
for(i=3;i<101;i++)
a[i]=(A*a[i-1]+B*a[i-2])%7;
for(i=1;i<55;i++)
{
if(mark[a[i]][a[i+1]]==0)
mark[a[i]][a[i+1]]=i;
else
{
cycle=i-mark[a[i]][a[i+1]];
break;
}
}
printf("%d\n",a[mark[a[i]][a[i+1]]-1+(n%cycle)]);
}
return 0;
}

Answer 1

寻找循环节点，最多49次
#include <stdio.h>
#include <string.h>
#include <math.h>
int f[1000];
int main()
{
int a,b,n,i,j;
int k[7][7];
f[1]=1;f[2]=1;
while (scanf("%d%d%d",&a,&b,&n),a||b||n)
{
memset(k,0,sizeof(k));
k[1][1]=2;
for (i=3;i<=50;i++)
{
f[i]=a*f[i-1]+b*f[i-2];
f[i]%=7;
if (k[f[i]][f[i-1]]) break;
k[f[i]][f[i-1]]=i;
}
j=i-k[f[i]][f[i-1]];
n-=k[f[i]][f[i-1]];
n%=j;
if (n==0) n+=j;
n+=k[f[i]][f[i-1]];
printf("%d\n",f[n]);
}
}