杭电ACM 1005 Number Sequence - neuxxm's Blog - 本为贵公子，平生实爱才。感时思报国，拔剑起蒿莱。

杭电ACM 1005 Number Sequence

neuxxm posted @ 2011年5月19日 22:35 in 杭电ACM 解题报告 with tags 数列数列_循环节 , 3791 阅读

Number Sequence

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

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>
#include <string.h>
int main(){
    int b[7][7];
    int a[100];
    int n;
    int x, y, m, st, len;
    while (scanf("%d %d %d", &x, &y, &m) == 3){
        if (x==0 && y==0 && m==0){
            break;
        }
        a[1] = 1;
        a[2] = 1;
        memset(b, 0, sizeof(b));
        b[1][1] = 1;
        n = 3;
        for (;;){
            a[n] = (a[n-1]*x+a[n-2]*y)%7;
            if (b[a[n-1]][a[n]] != 0){
                break;
            }
            b[a[n-1]][a[n]] = n-1;
            ++n;
        }
        st = b[a[n-1]][a[n]];
        len = n-1-st;
        if (m < st){
            printf("%d\n", a[m]);
        }
        else{
            printf("%d\n", a[st+(m-st)%len]);
        }
    }
    return 0;
}

全局相关文章
相关文章

杭电ACM 1021 Fibonacci Again