`
Simone_chou
  • 浏览: 182779 次
  • 性别: Icon_minigender_2
  • 来自: 广州
社区版块
存档分类
最新评论

Number Sequence(数学)

    博客分类:
  • HDOJ
 
阅读更多

Number Sequence

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 96275    Accepted Submission(s): 23088


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
 

       题意:

       给出 A (1 ~ 1000),B (1 ~ 1000),N (1 ~ 10 ^ 8),F [ 1 ] = F [ 2 ] = 1,后 F [ N ] =(A * F [ N - 1 ] + B * F [ N - 2 ] )% 7。输出 F [ N ]。

 

       思路:

       数学。结果 % 7,说明 f 最多也只可能是 0 ~ 6 中的某一个数,模拟几组数据即可发现会有循环节。算出循环节后 F [ N % MOD ] 即是答案。循环节最多也只可能是 7 X 7 = 49 这么多,所以数组开 55 来保存循环节也就够了。

 

       AC:

#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

int num[55];

int main () {
        int a, b, n;

        while (~scanf("%d%d%d", &a, &b, &n) && (a + b + n)) {
                int mod;
                num[1] = num[2] = 1;
                for (mod = 3; mod < 55; ++mod) {
                        num[mod] = (a * num[mod - 1] + b * num[mod - 2]) % 7;
                        if (num[mod] == 1 && num[mod - 1] == 1) {
                                mod -= 2;
                                break;
                        }
                }
                if (!(n % mod)) printf("%d\n",num[mod]);
                else printf("%d\n", num[n % mod]);
        }

        return 0;
}

 

 

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics