HDOJ1005 数列

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
 
我一开始写的程序如下,它的运算结果是对的,但是提交以后系统评判我运算超时了,后来一想确实是如此的。
 #include<iostream>
#include<cmath>
using namespace std; int myfunction( int A, int B, int n )
{
int counts = n-+;
int first=,second=,result;
for( int i=; i<counts; i++ )
{
result = (B*first+A*second)%; //大部分的时间都浪费在了这里
first = second;
second = result;
}
return result;
} int main(void)
{
int A,B,n; while()
{
cin>>A>>B>>n;
if( A== && B== && n== )
break;
if( n== || n== )
cout<<<<endl;
else
{
cout<<myfunction(A,B,n)<<endl;
}
}
return ;
}

其实这个数列是有规律的,只要算出它的一圈数列后,再算出n中有多少圈,之后就知道最终得出圈中哪个数。

例如输入1 2 10000后,数列的前几个数为1  1  3  5  4  0  1  1

它开始转圈了,因此我将程序改成如下所示:

 #include<iostream>
using namespace std;
int main()
{
int a,b,n,i,m,t[];
t[]=;
t[]=;
while(cin>>a>>b>>n)
{
if((a==)&&(b==)&&(n==))
break;
a=a%;
b=b%;
for(i=; i<; i++)
{
t[i]=(a*t[i-]+b*t[i-])%;
if((t[i]==)&&(t[i-]==))
{
break;
}
}
m=n%(i-);
if(m==)
cout<<t[i-]<<endl;
else
cout<<t[m]<<endl;
}
return ;
}

哈哈,AC了

这道题给我的提示是,遇到数列题目时要想想里面是不是存在“转圈”现象,发觉里面的规律,之后编程就容易了。

上一篇:codeforces 578b//"Or" Game// Codeforces Round #320 (Div. 1)


下一篇:【算法编程】基于Miller-Rabin的大素数测试