题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=1005

题目描述

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).

思路

看到这类题目数据规模那么大,暴力可能行不通,该找规律了。拒绝暴力!

看到求余运算,f(n)应该是个周期函数,周期跟A, B有关。

主要就是求出A, B对应的周期即可,剩下好办了。

AC代码

/*************************************************************************
    > File Name: 1005.cpp
      > Author: Netcan
      > Blog: http://www.netcan.xyz
      > Mail: 1469709759@qq.com
      > Created Time: Mon 11 May 2015 11:41:05 AM CST
 ************************************************************************/

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <sstream>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <stack>
#include <set>
#include <numeric>
#include <utility>
#include <cstring>
using namespace std;

int main()
{
    int A,B,N;
    int f[50];
    f[1] = 1;
    f[2] = 1;
    while(cin >> A >> B >> N && !(A==0 && B==0 && N==0)) {
        int T  = 2; // 周期初始化
        for(int i=3; i<=49; ++i) { // 最大周期应该小于等于7x7 = 49 
            f[i] = (f[i-1] * A + f[i-2] * B)%7;
            if(f[i] == f[i-1] && f[i] == 1) { // 找到周期
                --T; 
                break;
            }
            else ++T;
        }
        if(N%T==0) // 因为首项是从1开始的,所以当N%T==0的时候无意义,N%T应该等于T(最后一项)而不是0。
            cout << f[T] << endl;
        else
            cout << f[N%T] << endl;
    }
    return 0;
}