HDU 1005 Number Sequence

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   Author CHEN, Shunbao   Source ZJCPC2004 题目大意： 本体是给定F[1]=F[2]=1，通过输入A,B,N三个数的值，计算F[n]= f(n) = (A * f(n - 1) + B * f(n - 2)) % 7.A，B，N同时为0时结束程序，且规定了范围。 解题思路： 我个人在做本题的时候没有考虑太多，直接用数学的公式计算思维去做，难度不打，但是当我将程序放进去测试时总是提示超时，随后通过参考其他AC程序发现都是运用的周期来考虑，这样的考虑是为了减少计算复杂量，当输入的N很大时，N最大为100000000，这超出了数组空间范围，是不能处理的。所以周期的优势就体现出来了，而如何还继续使用直接的数学公式方法，则计算量会比周期的多很多，虽然结果都一样，但时间上，周期的算法会更好，这就是优化的问题。通过分析我们可以得到最终的结果只有0,1,2,3,4,5,6这几个数字，然而艰难的情况就是你需要计算49次才能找到正确的值，所以我们就以49作为一个周期，计算出一个周期内的所有结果，然后利用nI得到余数，此余数作为下标，输出结果。 #include<stdio.h> #include<math.h> int main() { int a,b,c,i,n; int fn[1000]; while(scanf("%d%d%d",&a,&b,&n)&&(a+b+n)) { fn[1]=1; fn[2]=1; if(n==1) { printf("%d\n",fn[1]); } if(n==2) { printf("%d\n",fn[2]); } if(n>2) { for(i=3;i<=48;i++) { fn[i]=(a*fn[i-1]+b*fn[i-2])%7; } c=nI; printf("%d\n",fn[c]); } } return 0; }