Number Sequence

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 159015    Accepted Submission(s): 39002 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   题解：f[n]每次都%7,那么这样就会有规律。所以先打表找到周期 注意：若A=B=0，则n>=3,f[n]=0;所以要进行判定； 找到周期的标志就是从i=3开始，若还有f[i]=f[i-1]=1,就开始了之前的循环。

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define CLR(a,b) memset(a,b,sizeof(a)) #define INF 0x3f3f3f3f #define LL long long int main() { int A,B,n; int f[220]; while(~scanf("%d%d%d",&A,&B,&n)) { bool flag=true; if(A==0&&B==0&&n==0) break; f[1]=f[2]=1; int i; for(i=3;i<=200;i++) //打表找到周期 { f[i]=(A*f[i-1]+B*f[i-2])%7; if(f[i]==1&&f[i-1]==1) //找到周期退出 break; if(f[i]==0&&f[i-1]==0) //A=B=0，则f[...]=0 { flag=false; break; } } if(i>n) // i 至少是 3，所以这一个判断应该在判断flag之前 { printf("%d\n",f[n]); continue; } if(!flag) { printf("0\n"); continue; } i-=2; //周期等于 i-2,减去的是后来相等的 i和i-1 n=n%i; if(n==0) n=i; printf("%d\n",f[n]); } return 0; }