关于HDOJ 1021题(Fibonacci Again) 的理解(C/C++)

和之前的1005很类似,遇到f(n)依赖前面项时的数列题  并且  涉及求余时，优先考虑找周期

题目描述

Fibonacci Again
  Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
  Total Submission(s): 82627 Accepted Submission(s): 37342

Problem Description
  There are another kind of Fibonacci numbers: F(0) = 7, F(1) = 11, F(n) = F(n-1) + F(n-2) (n>=2).

Input
  Input consists of a sequence of lines, each containing an integer n. (n < 1,000,000).

Output
  Print the word “yes” if 3 divide evenly into F(n).

  Print the word “no” if not.

Sample Input
  0
  1
  2
  3
  4
  5

Sample Output
  no
  no
  yes
  no
  no
  no

Author
  Leojay

原题链接

More info:Question

硬来？

  直接硬上……然而，事实证明博主太年轻太天真……

  WA警告教做人

#include<iostream>
using namespace std;
int f[1000001];
int n;
int main() {
    f[0] = 7; f[1] = 11;
    for (int i = 2; i < 1000001; i++) {
        f[i] = f[i - 1] + f[i - 2];
    }
    while (cin >> n) {
        if (f[n] % 3 == 0) cout << "yes" << endl;
        else cout << "no" << endl;
    }
    return 0;
}

Accepted代码

#include<iostream>
using namespace std;
int f[1000001];
int n;
int main() {
    int len_ =-1;
    f[0] = 7; f[1] = 11;
    for (int i = 2; i < 1000001; i++) {
        f[i] = f[i - 1] + f[i - 2];
    }
    for (int i = 0; i < 50; i++) {//实际开>9就行了
        f[i]= f[i] % 3 ;
        if (f[i]%3 == 1 && f[i + 1]%3 == 2 && i!=0) { 
            len_ = i;
            break;
        }
        
    }
    while (cin >> n) {
        n = n % len_;
        if (f[n] == 0) cout << "yes" << endl;
        else cout << "no" << endl;
    }
    return 0;
}

    f(n)的存储没必要直接用f(n),反正最后的结果是%3，干脆直接存为%3后的余数。由于f(n-1)、f(n-2)都属于（0,2）的整数，即都只有3中情况，所以f(n)应该只有3*3即9种可能情况。于是又循环找到周期len_,最后用n%len_(周期)，即可快速找到n是否可以整除3