菜鸟题解 HDU-1021 Fibonacci Again

原题直达

https://vjudge.net/contest/582185#problem/I

题干

原题面
参考翻译

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.

还有另一类斐波那契数:F(0) = 7, F(1) = 11, F(n) = F(n-1) + F(n-2) (n>=2)。

Input

输入由一系列行组成，每一行包含一个整数n。1000000)。

Output

如果3人平均分成F(n)，打印单词“yes”。

如果不是，打印单词“no”。

测试案例

Input

Output

no
no
yes
no
no
no

题意与思路

给定一个斐波那契数列：

F(0) = 7, \\F(1) = 11, \\F(n) = F(n-1) + F(n-2), n\geq2

求对于给定的 n ， $F(n)$ 是否能整除 3。

由于斐波那契数列的递推关系是加法，因此其对 3 的整除性 也具有加法的递推关系：

\begin{aligned} & F(i)\equiv a & \mod3\\ & F(i+1)\equiv b & \mod3\\ \Rightarrow & F(i+2)\equiv(a+b) & \mod3 \end{aligned}

手推几项找规律：

\begin{aligned} & F(0) = 7 &\equiv1 & \mod 3 \\ & F(1) = 11 &\equiv2 & \mod 3 \\ & F(2) = 18 &\equiv1+2 \equiv0 & \mod 3 \\ & F(3) = 29 &\equiv2+0 \equiv2 & \mod 3 \\ & F(4) = 47 &\equiv0+2 \equiv2 & \mod 3 \\ & F(5) = 76 &\equiv2+2 \equiv1 & \mod 3 \\ & F(6) = 123 &\equiv2+1 \equiv0 & \mod 3 \\ & F(7) = 199 &\equiv1+0 \equiv1 & \mod 3 \\ & F(8) = 322 &\equiv0+1 \equiv1 & \mod 3 \\ & F(9) = 521 &\equiv1+1 \equiv2 & \mod 3 \\ \end{aligned}

可以看出， $F(8)\equiv F(0)\equiv 1, F(9)\equiv F(1)\equiv2$ ，此后 $F(10)\equiv F(2),F(11)\equiv F(3),...$

周期为 8，当且仅当 $n\equiv2\mod8$ 或 $n\equiv 6\mod8$ 时 $F(n)\equiv0\mod3$ 。

题解

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

int n;

int main(){
    while (scanf("%d", &n) != EOF){
        if(n % 8 == 2 || n % 8 == 6)
            cout<<"yes"<<endl;
        else
            cout<<"no"<<endl; 
    }
    
    return 0;
}