Question

杭电ACM1005

求大神给看看哪里出问题啦，自我感觉挺好的，就是不能AC，谢谢
#include <iostream>
using namespace std;
int main()
{
int a,b,n;
int f(int,int,int);
int regular(int,int);
cin>>a>>b>>n;
while(a+b+n!=0)
{
if(n<50)
cout<<f(a,b,n)<<endl;
else
{
int r=regular(a,b);
int t=n%r;
if(t==0)
cout<<f(a,b,r)<<endl;
else
cout<<f(a,b,t)<<endl;
}
cin>>a>>b>>n;
}
return 0;
}

int f(int a,int b,int n)
{
if(n==1||n==2)
return 1;
else
{
int t1=1,t2=1;
for(int i=2;i<n;i++)
{
int t0=t2;
t2=(a*t2+b*t1)%7;
t1=t0;
}
return t2;
}
}

int regular(int a,int b)
{
for(int i=3;i<51;i++)
if(f(a,b,i)==1&&f(a,b,i+1)==1)
break;
return i-1;
}

Answer 1

你确定周期在50以内么？
你这里已经默认周期最大为50了。

你应该先求一下周期。
每个数出来的值都是7以内的，因为mod7
那你可以把连续二个值， xx 存起来， 建一个 int hash[100]的数组。

如果hash[xx]存在过了，就可以求出他的周期。

追问

你好，昨天楼下这位朋友这样给我解答的周期为什么是50之内，
你有什么别的看法咱可以讨论一下，
http://zhidao.baidu.com/question/573453994?quesup2&oldq=1

追答

周期是可以确认在50以内，但是没必要一开始就限死啊，首先循环不一定就是1 1 循环。

这题是一定要求出周期的，就让计算机自己计算出来不是更好，

Answer 2

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

追问

你好，我还想问一下我把那个寻找周期的函数设置为50之内有没有问题，为什么楼上说不能确定周期在50之内呀，

追答

周期50以内是一定的，你可以看看其他的AC代码 讨论区有很多
你这个代码的问题不在于判断周期 而是判断条件
就像是循环小数一样，肯定会循环，但不一定是纯循环小数，也就是说，不一定是从第一位开始循环的
比如我给你列的那个例子
A=121 B=21
数列是
1 1 2 4 1 2 4 ...
循环周期是3， 但按照你的查找方法，永远不会有下一个1 1序列出现，所以regular函数会在50后退出，得出一个循环周期50的错误答案

改正方法，不用函数，或者用函数参数带回两个值，一个是循环开始点，一个是循环周期
判断的时候，用数组保存序列，每算出一个值，都和之前序列比较，最终找到循环点及周期

Answer 3

你写的太麻烦啦，下面是我写的；可以参考参考；不懂的再问我；
#include<stdio.h>
int main()
{
int A,B,f[50],i,j;
long long n;
while(scanf("%d%d%lld",&A,&B,&n)!=EOF)
{
f[1]=1;f[2]=1;
if(A==0&&B==0&&n==0)break;
else{
for(i=3;i<50;i++)
{
f[i]=(A*f[i-1]+B*f[i-2])%7;
if(f[i]==1&&f[i-1]==1) break;
}
j=n%(i-2);
if(j==0){j=i-2;printf("%d\n",f[j]);}
else
printf("%d\n",f[j]);

}
}
return 0;
}