Question

杭电 acm 1005

刚接触ACM，在杭电 acm中提交之后，提示错误。有高手可以帮我指出吗？
Problem Description
A number sequence is defined as follows:
f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7.
Given A, B, and n, you are to calculate the value of f(n).
Input
The input consists of multiple test cases. Each test case contains 3 integers A, B and n on a single line (1 <= A, B <= 1000, 1 <= n <= 100,000,000). Three zeros signal the end of input and this test case is not to be processed.
Output
For each test case, print the value of f(n) on a single line.
Sample Input
1 1 3
1 2 10
0 0 0
Sample Output
2
5
我的代码是这样的：
#include <stdio.h>
void main()
{
long n;
int a,b;
long f1,f2,fn,fa[50000],j;
scanf("%d%d%ld",&a,&b,&n);
while(a||b||n)
{
fa[0]=fa[1]=f1=f2=1;
j=2;
while(1)
{
fa[j++]=fn=(a*f2+b*f1)%7;
f1=f2;
f2=fn;
if(f1==1&&f2==1)
break;
}
j=j-2;
n=(n-1)%j;
printf("%d\n",fa[n]);
scanf("%d%d%ld",&a,&b,&n);
}
}
可以帮我分析一下我写的这个程序吗?我想知道我的程序错在什么地方了.谢谢!

Answer 1

#include <iostream>
using namespace std;

int main()
{
int f[100];
long A,B,n;
int r;
f[0]=f[1]=1;
cin >> A >> B >> n;
while(A&&B&&n)
{
int i=2;
r = 7;
while(true)
{
if(i==n) break;
f[i] = (A*f[i-1]+B*f[i-2])%7;
int j;
for(j=i-1;j>0;j--)
{
if(f[j]==f[i]&&f[j-1]==f[i-1]) break;
}
if(j==0) i++;
else
{
r = f[(n-1-i)%(i-j)+j];
break;
}
}
if(r==7) cout << f[n-1] << endl;
else cout << r << endl;
cin >> A >> B >> n;
}
return 0;
}
Run ID Submit Time Judge Status Pro.ID Exe.Time Exe.Memory Code Len. Language Author
1474226 2009-07-13 00:20:16 Accepted 1005 0MS 344K 532 B C++ Parker

#include <stdio.h>

int main()
{
int f[100];
long A,B,n;
int r,j;
f[0]=f[1]=1;
scanf("%d%d%ld",&A,&B,&n);//cin >> A >> B >> n;
while(A&&B&&n)
{
int i=2;
r = 7;
while(1)
{
if(i==n) break;
f[i] = (A*f[i-1]+B*f[i-2])%7;
for(j=i-1;j>0;j--)
{
if(f[j]==f[i]&&f[j-1]==f[i-1]) break;
}
if(j==0) i++;
else
{
r = f[(n-1-i)%(i-j)+j];
break;
}
}
if(r==7) printf("%d\n",f[n-1]);//cout << f[n-1] << endl;
else printf("%d\n",r);//cout << r << endl;
scanf("%d%d%ld",&A,&B,&n);
}
return 0;
}

1474249 2009-07-13 00:26:22 Accepted 1005 0MS 220K 573 B C Parker

Answer 2

来个矩阵幂二分加速的代码吧。。。
#include<iostream>
using namespace std;
int a1,a2,b1,b2,ans_1,ans_2;
void ans_mul_mat()
{
int _ans_1,_ans_2;
_ans_1=(ans_1*a1+ans_2*b1)%7;
_ans_2=(ans_1*a2+ans_2*b2)%7;
ans_1=_ans_1;
ans_2=_ans_2;
}
void mat_mul_mat()
{
int x[5];
x[1]=(a1*a1+a2*b1)%7;
x[2]=(a1*a2+a2*b2)%7;
x[3]=(b1*a1+b2*b1)%7;
x[4]=(b1*a2+b2*b2)%7;
a1=x[1];
a2=x[2];
b1=x[3];
b2=x[4];
}
int main()
{
int a,b,n;
while(scanf("%d%d%d",&a,&b,&n)&&(a||b||n))
{
a1=0,a2=b;
b1=1,b2=a;
ans_1=ans_2=1;
n--;
while(n)
{
if(n&1)
ans_mul_mat();
mat_mul_mat();
n>>=1;
}
printf("%d\n",ans_1%7);
}
}