水题 | HDU 1021

Fibonacci Again

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

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1021

解题思路

首先，这是一道水题，直接根据递推式，逐步递推算出各个的值，再判断即可。(因为n的值比较小，所以可以暴力过，但是当n的值更大时，极有可能TLE)

方法一：暴力递推

#include <stdio.h>
int f[1000010];

int main()
{
    int n;
    f[0]=1; f[1]=2;
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=2;i<=n;i++)
        {
            f[i] = (f[i-1]+f[i-2])%3;
        }
        if(f[n]%3==0)printf("yes\n");
        else printf("no\n");
    }
    return 0;
}

方法二：矩阵快速幂

在学习了矩阵快速幂之后，当看到递推式时，我们就会自然联想到利用矩阵乘法，构造出矩阵幂次，利用矩阵快速幂进行计算。(没上注释，不懂的童鞋先学一下矩阵快速幂)

// 矩阵快速幂入门
// HDU 1021 
// 15MS 1384K 921B G++

#include<iostream>
#include<cstdio>
using namespace std;
long long mod=3;

struct Mat
{
    long long mat[2][2];
};

Mat multiply(Mat A,Mat B)
{
    Mat temp;
    for(int i=0;i<2;i++)
    {
        for(int j=0;j<2;j++)
        {
            temp.mat[i][j]=0;
            for(int k=0;k<2;k++)
            {
                temp.mat[i][j]=(temp.mat[i][j]+A.mat[i][k]*B.mat[k][j])%mod;
            }
        }
    }
    return temp;
}

Mat operator^(Mat A,int k)
{
    Mat base;
    base.mat[0][0]=base.mat[1][1]=1;
    base.mat[1][0]=base.mat[0][1]=0;
    while(k)
    {
        if(k&1)base=multiply(base,A);
        A=multiply(A,A);
        k=k>>1;
    }
    return base;
}

int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        if(n<2)
        {
            printf("no\n");
        }
        else
        {
            Mat ans;
            ans.mat[1][1]=0;
            ans.mat[0][0]=ans.mat[0][1]=ans.mat[1][0]=1;
            ans=ans^(n-1);
            long long sum=ans.mat[0][0]*11+ans.mat[0][1]*7;
            if(sum%3==0)printf("yes\n");
            else printf("no\n");
        }
    }
}

方法三：找规律

这样我们就得到了如下规律：从第2个开始每隔4个循环一次，即(n%4)==2,输出yes。

// 找规律
// n%4==2 => yes 
//0MS 1376K 203B G++
#include <cstdio>
#include <iostream>
using namespace std;
int main() 
{
    int n;
    while(~scanf("%d",&n))
    {
        if(n%4==2)puts("yes");
        else puts("no");
    }
    return 0;
}

方法四：找规律，循环节

在第三种方法的基础上，我又发现了另一种规律：

索引从 0~7 、 8~15 ……依次呈现“no、no、yes、no、no、no、yes、no”的结果，（索引即上图中的index，也就是n的值）而且我们发现当索引n mod 8的值等于2和6的时候，输出yes，其他输出no。

// 【循环节】【找规律】 
// 这个题的循环节是8，每8个循环一次
// n%8:0~7 
// 15MS 1376K 200B G++
#include<iostream>
#include<cstdio>
using namespace std;

int main()
{
    int n,ans;
    while(~scanf("%d",&n))
    {
        ans=n%8;
        if(ans==2 || ans==6)printf("yes\n");
        else printf("no\n");
    }
}

写在最后

参考资料：

• 博客：https://blog.csdn.net/lvshubao1314/article/details/38019125?utm_source=blogxgwz1
• 博客：https://blog.csdn.net/oliver233/article/details/49307835

虽然是水题，但是发散了思维，一题多解。

如有其他解法，欢迎指教。