条件:f(n)=A*f(n-1)+B*f(n-2)%7,f(1)=1,f(2)=1 多组测试输入:A,B,n(n=0结束，0<=1000<=1000,1<=n<=100000000) 输出:f(n) 注意：直接递归必定超时。 解题思路：因为f(n)的值必定为0,1,2,3,4,5，6,中的一个，所以f(n)存在7*7=49种值，所以在经过50次递归后必定已经进入循环。 解题代码: #include #include using namespace std; int A,B,a[55][2],m1,m2; int f() { int summ; bool flag=false; a[3][0]=1; a[3][1]=1; for(int i=4;i<=100;i++) { summ=(a[i-1][1]*A+B*a[i-1][0])%7; a[i][0]=a[i-1][1]; a[i][1]=summ; for(int j=3;j<=i-1;j++) if(a[i][0]==a[j][0]&&a[j][1]==a[i][1]) { m1=j; m2=i-1; flag=true; } if(flag==true) break; } return 0; } int main() { int n,summ,m; while(scanf("%d%d%d",&A,&B,&n)!=EOF&&n!=0) { if(n==1||n==2) { printf("1 "); continue; } f(); if(n<=m2) summ=(A*a[n][1]+B*a[n][0])%7; else { m=m2-m1+1; n=(n-m2-1)%m+m1; summ=(A*a[n][1]+B*a[n][0])%7; } printf("%d ",summ); } return 0; }