Question

杭电ACM1005

杭电有没有用C语言写的，我的超时~~int f(int A, int B) {
int a, b, c, i;
a = 1;
b = (A + B) % 7;
for(i = 4; i <= 100; i++) {
c = (A * b + B * a) % 7;
a = b;
if(c == 1 && a == 1) {
int T = i - 2;
return T;
}
b = c;
}
return 1;
}
int main() {
int A, B, n;
while(scanf("%d%d%d", &A, &B, &n) == 3) {
if(!A && !B && !n)
break;
int T = f(A, B);
arr[1] = arr[2] = 1;
int tmp = n % T;
for(int i = 3; i <= tmp; i++)
arr[i] = (A * arr[i - 1] + B * arr[i - 2]) % 7;
printf("%d\n", arr[tmp]);
}
return 0;
}
#include<stdio.h>
#include<math.h>
void main()
{
long int n;
int a,b;
int f(long int n,int a,int b);
while(scanf("%d%d%ld",&a,&b,&n)!=EOF)
{
if((a==0&&b==0&&n==0)||a<1||b>1000||n<1||n>100000000) break;
else printf("%d\n",f(n,a,b));
}
}
int f(long int n,int a,int b)
{ int fac;
if(n==1) return fac=1;
else if(n==2) return fac=1;
else return fac=((a*f(n-1,a,b)+b*f(n-2,a,b)))%7;
}这个才是我的

Answer 1

// 每个数据都走那么多肯定是TLE啦，这题是有周期的。
// 下面是我的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

regular判断函数有问题
周期肯定存在，但不一定是从1
1开始
反例数据
121
21
100
你的代码结果，1
ac代码结果
4