题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1005
解题思路：显然，直接迭代会 TLE , 由于结果 mod 7 , 故 f(i), f(i+1) 的状态 (f(i),f(i+1)) 最多只有 7×7=49 种，可先求循环节长度，减少不必要的计算。注意：循环节不一定从 (1,1) 开始。
1 /////////////////////////////////////////////////////////////////////////// 2 //problem_id: hdoj 1005 3 //user_id: SCNU20102200088 4 /////////////////////////////////////////////////////////////////////////// 5 6 #include <algorithm> 7 #include <iostream> 8 #include <iterator> 9 #include <iomanip> 10 #include <cstring> 11 #include <cstdlib> 12 #include <string> 13 #include <vector> 14 #include <cstdio> 15 #include <cctype> 16 #include <cmath> 17 #include <queue> 18 #include <stack> 19 #include <list> 20 #include <set> 21 #include <map> 22 using namespace std; 23 24 /////////////////////////////////////////////////////////////////////////// 25 typedef long long LL; 26 const double PI=acos(-1.0); 27 /////////////////////////////////////////////////////////////////////////// 28 29 /////////////////////////////////////////////////////////////////////////// 30 //Add Code: 31 /////////////////////////////////////////////////////////////////////////// 32 33 int main(){ 34 /////////////////////////////////////////////////////////////////////// 35 //Add code: 36 int A,B,n,i,f[55],a[7][7]; 37 while(scanf("%d%d%d",&A,&B,&n)!=EOF){ 38 if(!(A||B||n)) break; 39 A%=7,B%=7; 40 memset(a,0,sizeof(a)); 41 f[1]=f[2]=1; 42 i=1; 43 while(a[f[i]][f[i+1]]==0){ 44 a[f[i]][f[i+1]]=i; 45 f[i+2]=(A*f[i+1]+B*f[i])%7; 46 i++; 47 } 48 int k=i-1; //第一个循环节的最后一个元素的下标 49 int len=i-a[f[i]][f[i+1]]; //循环节长度 50 n-=(n-k)/len*len; 51 if(n>k) n-=len; 52 printf("%d ",f[n]); 53 } 54 /////////////////////////////////////////////////////////////////////// 55 return 0; 56 } 57 58 /////////////////////////////////////////////////////////////////////////// 59 /* 60 Testcase: 61 Input: 62 1 1 3 63 1 2 10 64 0 0 0 65 Output: 66 2 67 5 68 */ 69 ///////////////////////////////////////////////////////////////////////////