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).
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了
这道题给我的提示是，遇到数列题目时要想想里面是不是存在“转圈”现象，发觉里面的规律，之后编程就容易了。