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
1 /* 2 一开始没看到n<=10000000 3 结果疯狂TLE 4 5 最后看了discuss 才知道要找周期 6 */ 7 #include8 #include 9 #define MAXN 10000001010 11 using namespace std;12 13 int a,b,n;14 15 int f[1001];16 17 int main() {18 while(~scanf("%d %d %d",&a,&b,&n)&&a&&b&&n) {19 int pos;20 f[0]=0;f[1]=1;f[2]=1;21 for(int i=3;i<=100;i++) {22 f[i]=(f[i-1]*a+f[i-2]*b)%7;23 if(f[i]==f[2]&&f[i-1]==f[1]) { //找到周期 24 pos=i;25 break;26 }27 }28 // printf("%d\n",pos-2);29 n=n%(pos-2); //周期为pos-2 30 if(n!=0) printf("%d\n",f[n]);31 else printf("%d\n",f[pos-2]);32 }33 return 0;34 }
Recommend
JGShining | We have carefully selected several similar problems for you: