題目鏈接： http://acm.hdu.edu.cn/showproblem.php?pid=1005

Number Sequence

Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 85249????Accepted Submission(s): 20209

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

解析：

這是一道尋找循環點的問題，可能很多人在杭電上通過了這個題目，但是我建議大家將自己的代碼再貼到另一個OJ上進行測試 http://zju.acmclub.com/index.php?app=problem_title&id=1&problem_id=2603 。

很多人都認為周期是49，但是給出的解題報告都不是很有說服力。

所以，我們可以尋找循環的開頭以及周期，然后輸出，這樣能夠保證正確性，當然一開始的記錄數組最好能夠相對大一些，不然仍然不能通過測試。

代碼：

    #include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <math.h>

#define min(a,b) (a<b?a:b)

#define max(a,b) (a>b?a:b)

#define swap(a,b) {(a)=(a)^(b); (b)=(a)^(b); (a)=(a)^(b);}

#define MAXN 65535

#define INF 1e9



int f[1200];

int main(){

    int a,b,n;

    int i, j;

    int flag, term, temp, begin;

    while(~scanf("%d%d%d", &a, &b, &n), (a||b||n)){

        memset(f, 0, sizeof(f));

        f[1]=1;

        f[2]=1;

        term = n;

        flag = 0;

        for(i=3; i<=n&&!flag; i++){

            f[i] = (a*f[i-1]+b*f[i-2])%7;

            for(j = 2; j<i; j++){

                if(f[i]==f[j]&&f[i-1]==f[j-1]){

                    term = i-j;

                    begin = j-2;

                    flag = 1;

                    break;

                }

            }

        }

        if(flag)

            printf("%d\n", f[begin+(n-1-begin)%term+1]);

        else

            printf("%d\n", f[n]);

    }

    return 0;

}

1005 Number Sequence（HDU）

更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索：z360901061

微信掃一掃加我為好友

QQ號聯系： 360901061

您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。

【本文對您有幫助就好】元

2元

5元

10元

20元

自定義