Number Sequence
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 89984 Accepted Submission(s): 21437
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
1 2 10
0 0 0
Sample Output
2
5
5
Author
CHEN, Shunbao
Source
Recommend
这道题足足提交了18遍，虽然是水题，但做的时候也要小心。
题目描述里提供有递归公式，但是万万不能用递归做，下面n的规模是10^8，用递归铁定超时。
需要先找到变化周期，周期是从f1=1，f2=1开始，到再遇到两个连续的1的时候停止。 记录下这个周期，剩下的就好做了。
不知道为什么，循环找周期的时候，for(i=3;i<10000;i++)，i<10000改成i<=10000就提交WA，难道它还会跑到i=10000？？
/*
这题不能直接按公式用递归来求，因为n最大可以达到100,000,000，会栈溢出
所以要找规律
前两个等于1，所以后面如果有两个连着的1出现，那就是出现周期了
*/
#include <iostream> using namespace std;
int t[];
int main()
{
int A,B,n;
t[]=t[]=;
while(cin>>A>>B>>n,A||B||n){
int i;
for(i=;i<;i++){
t[i]=(A*t[i-]+B*t[i-])%;
if(t[i]== && t[i-]==){
break;
}
}
n=n%(i-);
t[]=t[i-];
cout<<t[n]<<endl;
}
return ;
}
Freecode : www.cnblogs.com/yym2013