HDU 1005 Number Sequence

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

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

这道题...好忧伤啊...做的时候根本没在意，感觉就是一个大循环，前面的数模 7 以后结果可能是 0-6，第二个数也是 0-6，所以有 7 * 7 = 49 种可能，就直接觉得一次循环就是49了...最坑的是杭电这道题的测试数据特别水，居然让我给过了 TAT...
然后给学校网站出题的时候直接用了这道题，提交了一些但是没有人对...有同学给我说可能数据错了...然后我才发现我的做法本身就有问题 TAT...

下面是我目前觉得应该是正确的代码...看不懂的话最后面有图解...如果还是错了的话..希望能有人给我说...虽然..咳咳..应该没人会看的吧TAT

#include <iostream>
#include <cstdio>
using namespace std;

int arr[100] = {0, 1, 1};

int main(int argc, const char * argv[]) {
    
    int a = 0, b = 0, n = 0;
    while (~scanf("%d%d%d", &a, &b, &n)
           && (a + b + n)) {
           
        // 查找一次循环的个数
        int flag = 0;
        int i = 3, j = 2;
        for (; i <= n; ++i) {
            arr[i] = (a * arr[i - 1] + b * arr[i - 2]) % 7;
            // 从前面找起，若有两个连续的数完全相同，则开始循环
            // 不用因为两层循环而担心时间的问题，因为这个循环次数特别少
            for (j = 2; j < i; ++j) {
                if (arr[i] == arr[j] && arr[i - 1] == arr[j - 1]) {
                    flag = 1;
                    break;
                }
            }
            if (flag) break;
        }
        // 当循环结束时，i - 2 ，去掉了最后两个重复的数
        if (n > j) {
            arr[0] = arr[i - 2];
            // i - j 去掉了开头一部分可能没有被循环起来的数
            i -= j;
            // (n - j) % i 后结果为，查看又循环到了第几个数
            // 但是别忘记，再加上 j ，因为还有开头的数得再加上
            cout << arr[(n - j) % i + j] << endl;
        } else {
            cout << arr[n] << endl;
        }
    }
    return 0;
}

图解：

emmmm...感觉和网上的做法也不太一样...虽然我也没太仔细看网上的做法..然后自己想了下，觉得这么做可能对的吧.....