首页 > 代码库 > HDU1005
HDU1005
Number Sequence HDU-1005
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 162730 Accepted Submission(s):
40016
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).
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
发这道题主要是祭奠一下我第一次遇到的超内存MLE。。。。。第一想法这么简单,暴力递归。。然后MLE狠狠打脸。。
后来再认真读题,发现还是有规律的。
如果f(n - 1)和f(n)都为1的话,就是一个循环。
#include <iostream> #include <cstdio>
using namespace std; int f[51]; int main() { int a, b; long long n; while (scanf("%d %d %lld", &a, &b, &n) == 3) { if (a == 0 && b == 0 && n == 0) break; f[1] = f[2] = 1; int i; for (i = 3; i < 51; i++) { f[i] = (a * f[i - 1] + b * f[i - 2]) % 7; if (f[i] == 1 && f[i - 1] == 1) //找到循环因子 i { break; } } n = n % (i - 2); if (n == 0) //刚好经过一个循环 printf("%d\n", f[i - 2]); else printf("%d\n", f[n]); } return 0; }
这题真的是好烦。。。。。。。
HDU1005
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。