HDU_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

Sample Output

2

5

首先想到了暴力：

#include<stdio.h>

int main(void)

{

    int a, b, n;

    int f1, f2, f3;

    while()

    {

        scanf("%d%d%d", &a, &b, &n);

        if(a== && b== && n==)

            break;

        f1 = ;

        f2 = ;

        f3 = ;

        for(int i = ; i <= n; i++)

        {

            f3 = (a*f2 + b*f1)%;

            f1 = f2;

            f2 = f3;

        }

        printf("%d\n", f3);

    }

    return ;

}

可惜暴力的后果是WA，再仔细看一下数据范围，n的取值达到一亿。由于数据范围很大，因此这题不适合暴力。

那么这道类似斐波那契数列的题目该如何搞呢？很明显，f(n-1)和f(n-2)的取值只可能有0, 1, 2, 3, 4, 5, 6这七种情况。因此f(n-1)+f(n-2)的组合一共有7*7种情况，这说明什么呢？说明数列（以f3作为第一个数）出现循环最多在第50个数（最坏的情况，可由鸽巢原理得出）。

修改后的程序：

#include<stdio.h>

int main(void)

{

    int f1, f2, a, b, n, i;

    int arr[]; // 空间够用的话多开点没坏处

    while()

    {

        scanf("%d%d%d", &a, &b, &n);

        if(a ==  && b ==  && n == )

            break;

        f1 = f2 = ;

        for(i = ; ; i++) // 一定会结束，因为最多在第50个数出现循环，其中i-1是循环周期

        {

            arr[i] = (a*f2 + b*f1)%;

            f1 = f2;

            f2 = arr[i];

            if(i >=  && arr[i-] == arr[] && arr[i] == arr[] )

                break;

        }

        if(n ==  || n == )

            printf("1\n");

        else

            printf("%d\n", arr[(n-)%(i-)]);

    }

    return ;

}

巴特西

HDU_1005:Number Sequence

最新文章

热门文章