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)是一个递推式，A、B为两个输入的参数，n表示迭代次数。以平常接数学题目时的思维来看，很简单，直接套公式，迭代n次肯定可以得到结果，下面是c语言实现代码：
#include "stdio.h"
#pragma warning(disable:4996)
int main()
{
int a, b;
long n;
long i;
int f[100];
f[0] = 1;
f[1] = 1;
while (scanf("%d %d %d", &a, &b, &n))
{
if (a < 1 || b > 1000 || n < 1 || n > 100000000)
return -1;
for (i = 2;i < n;i++)
{
f[i] = a * f[i - 1] + b * f[i - 2];
f[i] = f[i] % 7;
}
printf("%d
", f[n-1]);
}
return 0;
}然而，考虑到n的次数很大时，迭代次数也增加到相当大，其运算很明显会占用大量的时间。所以需要考虑响应的方法减小计算量，加快程序运行速度。
我们可以观察到公式所有的值都是经过mod7 运算的，通过对7取余，我们可以知道递推结果的数列中每个值的大小都是0~6。每位有7种可能情况，递推公式中有两个数列的值输入，所以有7*7=49 种可能的组合。在所有的组合都出现之后，下一个情况必定是前面出现过的组合中的某一种，一次类推，重复出现，由此可以求到循环的周期。
利用循环周期，就可以很轻松地计算得到第n个对应哪一种情况了。
废话不多说，直接上代码吧。
#include "stdio.h"
#pragma warning(disable:4996)
int main()
{
int a, b, n;
int f[54] = { 0,1,1 };
int pos;
while (scanf("%d %d %d", &a, &b, &n) != EOF)
{
if (a < 1 || b > 1000 || n < 1 || n > 100000000)
return -1;
for (int i = 3;i < 54;i++)
{
f[i] = (a * f[i - 1] + b * f[i - 2]) % 7;
//printf("%d ", f[i]);
if (i > 5)
{
if (f[i - 1] == f[3] && f[i] == f[4])
{
pos = i - 4;
break;
}
}
}
//printf("
");
if (n > 2)
printf("%d
", f[(n-3) % pos+3]);
else
printf("1
");
}
return 0;
}补充：
- 为计算方便，从数组下标为1的元素对应数列第一个数，舍弃下标为0的那个元素；
- 关于循环，网上很多程序都是检测到前后两个分别为1、1的情况时就认为开始下一轮循环了；然而这种方法是错误的，因为如果取特例a=7、b=7时，输出序列为：1、1、0、0、0。。。。后面全部是0，这样程序会持续运行下去，因为不可能再检测到1、1了；所以检测循环时从第3个和第4个开始，检测是否重复：
if (f[i - 1] == f[3] && f[i] == f[4])
{
pos = i - 4;
break;
}