Number Sequence
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 225136 Accepted Submission(s): 57138
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 0Sample Output
2 5 这是一道水题，但是由于菜鸡的我并不清楚到底要循环几次就束手无策，因为从1e8的范围就可以看出来，暴力一定会超时（1e8跑一遍差不多1s，但是不可能跑一遍就出来） 后来通过查题解知道了原来确实结果是循环（不然真的难办），但是循环次数最多也是49次，怎么算的呢？因为一组数据里面A，B的值是一定的，当f(n - 1)和f(n - 2)相同时，后面的结果就和之前一样，接下来就是开始循环了。于是乎，网上有题解n % 49的有，循环找f(n - 1), f(n - 2)都为1作为跳出找到循环节的也有，可是，这些都没考虑到当循环是11232323.......这样的（确实可以做得到，因为A，B每组数据不一定），找什么f(n - 1), f(n - 2)都为1，找什么49，都是错的，所以还得统计之前出现过的两位即可，我们开个int二维数组记录，数组的值是第一次出现的两个数后一个的位置，若为0则没出现。#include <stdio.h>
#include <string.h>
int arr[100];
int k[7][7];
int main(void)
{
int a, b, n;
while(scanf("%d %d %d", &a, &b, &n) == 3 && (a || b || n))
{
memset(k, 0, sizeof(k));
int i;
arr[1] = arr[2] = 1;
k[1][1] = 2;
for(i = 3; i < 70; i++)
{
arr[i] = (a * arr[i - 1] + b * arr[i - 2]) % 7;
if(!k[arr[i]][arr[i - 1]])//这两个排列没出现过
k[arr[i]][arr[i - 1]] = i;//标记第一次出现的位置
else//出现过
break;//那就找到了循环节，因为后面就一直重复第一次的位置到现在的位置中间的数字
}
int m = k[arr[i]][arr[i - 1]];//m没啥意义，就是写k[arr[i]][arr[i - 1]]太麻烦了
int t = i - m;//找到循环位数
if(n <= m)//如果在之前，在循环之前，直接输出
printf("%d\n", arr[n]);
else//在后面，则在循环节中某一个值
printf("%d\n", arr[(n - m) % t + m]);
}
return 0;
}
杭电讨论板块网友提供的测试数据（因为题目的测试数据很水，% 49找1 1都能过）
247 602 35363857 376 392 9671521 759 623 18545473 53 399 46626337 316 880 10470347 0 0 0 ------------------------------------------------------------------------------ Output: 4 3 5 2 3 |