Question

求一道C++题目

f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7.
每个测试用例包含3个整数A,B和n在一行(1 < = A、B < = 1000,1 < = n < = 100000000)，A=B=n=0时结束程序，求f（n）
用C++编写。要求运行时间要很短。

Answer 1

这个数列是有周期的，计算一个周期的数据就好（因为想不出计算周期数的数学方法，就暴力计算出一个周期的）

#include <iostream>
#include <vector>
#include <ctime>
using namespace std;
int main()
{
	int  A, B, n;	
	cin >> A >> B >> n;	
	vector<int> f;
	f.push_back(999);
	f.push_back(1);	
	f.push_back(1);
	int i = 3;
	int fg = 0;
	time_t  t= clock();
	while (i <= n)
	{
		f.push_back((A*f[i-1]+B*f[i-2])%7);
		if (f[i] == 1 && f[i - 1] == 1)   //再一次出现连续的两个1,周期长度就是i-2
		{
			fg = 1;
			break;
		}			
		++i;
	}
	t = clock() - t;
	cout <<( fg ? f[n % (i - 2)] : f[i - 1] )<< endl<<"用时:"<<t<<"毫秒"<<endl;
	return 0;
}

Answer 2

#include<iostream>
using namespace std;
int f(int a,int b,int n) {
  if ( n==1 || n==2 ) return 1;
  else return(a*f(n-1)+b*f(n-2))%7;
}
void main() { int A,B,n,y;
  while ( 1 ) {
    cin>>A>>B>>n; if ( A==0 && B==0 && n==0 ) break;
    y=f(A,B,n); cout<<y<<endl;
  }
}