HDU 1005（周期問題），hdu1005周期問題

                                    HDU 1005

Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u  

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  

題解：

一開始看到這題我就直接跳過了。。

但是後來發現還是有些規律的，對於f[n-1] 或者 f[n-2] 的取值只有 0,1,2,3,4,5,6 這7個數，A，B又是固定的，所以就只有49種可能值了。由該關系式得知每一項只與前兩項發生關系，所以當連續的兩項在前面出現過循環節出現了，注意循環節並不一定會是開始的 1，1 。 又因為一組測試數據中f[n]只有49中可能的答案，最壞的情況是所有的情況都遇到了，那麼那也會在50次運算中產生循環節。找到循環節後，就可以解決此題

注意：周期的大小，有可能是大周期，有可能是小周期！

#include<iostream>
using namespace std;

int f[54]={0,1,1};
int main()
{
	
    int A,B,n,q=1;	
while(cin>>A>>B>>n&&A&&B&&n)
	{
	for(int i=3;i<54;++i)
{ 
	f[i]=(A*f[i-1]+B*f[i-2])% 7;
if(i>4)                         
{if(f[i-1]==f[3]&&f[i]==f[4])
		{	
			q=i-4;  //要特別注意，可以想一下為什麼？
		
		}  
}	
	}	
cout<<f[n%q]<<endl;	
 
}

return 0;
}