Number Sequence
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 106254 Accepted Submission(s): 25842
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
Recommend
JGShining | We have carefully selected several similar problems for you: 1004 1021 1019 1002 1012
打表找规律, 只要考虑A B 在1--7之间的情况就行了
#include<map> #include<set> #include<list> #include<stack> #include<queue> #include<vector> #include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int xunhuan[100]; int main() { int a, b; int n; while(~scanf("%d%d%d", &a, &b, &n)) { if(!a && !b && !n) break; if(n == 1 || n == 2) { printf("1\n"); continue; } if(a == 7 && b == 7) { printf("0\n"); continue; } if((a == 1 && b == 7) || (a == 7 && b == 1)) { printf("1\n"); continue; } if(a == 2 && b == 7) { int a[3] ={4, 1, 2}; printf("%d\n", a[(n - 1) % 3]); continue; } if(a == 3 && b == 7) { int a[6] = {5, 1, 3, 2, 6, 4}; printf("%d\n", a[(n - 1) % 6]); continue; } if(a == 4 && b == 7) { int a[2] = {2, 4}; printf("%d\n", a[(n - 1) % 2]); continue; } if(a == 5 && b == 7) { int a[6] = {3, 1, 5, 4, 6, 2}; printf("%d\n", a[(n - 1) % 6]); continue; } if(a == 6 && b == 7) { int a[6] = {6, 1}; printf("%d\n", a[(n - 1) % 2]); continue; } xunhuan[1] = 1; xunhuan[2] = 1; int cnt = 2; int fn1 = (a + b) % 7; int fn2 = (a * fn1 + b) % 7; while(fn1 != 1 || fn2 != 1) { xunhuan[++cnt] = fn1; xunhuan[++cnt] = fn2; int tmp2 = fn2; fn1 = (a * tmp2 + b * fn1) % 7; fn2 = (a * fn1 + b * tmp2) % 7; } xunhuan[0] = xunhuan[cnt]; printf("%d\n", xunhuan[n % cnt]); } return 0; }