[hdoj_1005]Number Sequence
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
2 5
题目大意：
1.多组测试数据，依次输入A,B,n(1 <= A, B <= 1000, 1 <= n <= 100,000,000)，输入0 0 0 终止；
2.f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7；
3.输出 f(n)。
解题思路：
1.n的数值很大，这类数值很大的问题一般都有规律，找出循环节（周期）是关键；
2.找规律，这道题是从 f(1) = 1 和 f(2) = 1 开始，然后依次模7，可知 f(n) 只有7种情况，所以两数相邻只有7*7=49种；
3.所以从 f(1) 到 f(49) 必会出现相邻两个 f(m-1) = 1 , f(m) = 1，所以 f(n) 为周期函数，49为其一个周期；
需要注意的地方：
做题的时候不要盲目的上手去做，先要仔细分析题目，先动脑再动手。
代码如下：
// hdoj_1005 Number Sequence
// 31MS 220K 370 B GCC
#include
int fun(int a, int b, __int64 n);
int main(void)
{
int a, b;
__int64 n;
while(scanf("%d%d%I64d", &a, &b, &n) && a != 0 && b != 0 && n != 0)
{
printf("%d
", fun(a, b, n%49));
}
return 0;
}
int fun(int a, int b, __int64 n)
{
if(n == 1 || n == 2)
return 1;
else
return (a*fun(a, b, n-1) + b*fun(a, b, n-2)) % 7;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
HDU 1421 침실 문제 풀이 보고서침실 을 옮 기 는 것 은 매우 힘 들 었 습 니 다. 그날 xhd 는 어 쩔 수 없 이 27 번 건물 에서 3 번 건물 로 옮 겨 야 했 습 니 다. 침실 안의 n 가지 물건 을 보고 xhd 는 멍 해 지기 시 작...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
