hdu 1005:Number Sequence(水题)

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
 
Sample Output
2
5
 
Author
CHEN, Shunbao
 
Source
 
Recommend
JGShining   |   We have carefully selected several similar problems for you:  1004 1019 1009 1012 1071 
 
  这道题足足提交了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

上一篇:MATLAB的符号计算


下一篇:Matlab与微积分计算