Blog·Tanky WooABOUTRSS

HDOJ 1021 Fibonacci Again

12 Jul 2010
这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。

1.首先,他只要判断是否可以被3整除,所以不需要求出每个数的真实值,只需要求出每个数除以3的结果,只有0,1,2三种情况。 2.我们令a[i]=m, a[i+1]=n(m, n=0, 1, 2) 所以a[i][ai+1]组成的二位数组合只有3*3=9种情况,也就是说,最多再过9个数,就是一次循环。及a[i][i+1] == a[j]j+1 3.然后你就可以求出循环t,接下来就是把n对t求余,最后…

大家无视下面被划横线的话~~~

这题本来是准备用hash数组加递推求的。

后来WA了,测试后才发现fib[999999]超过了long long范围,所以此法不可取。

在网上参考了下别人的方法,发现,居然是罗列前十几个fib[i]%3的结果找规律,发现是以8为周期。 不太习惯这种题。感觉没意义。

// HDOJ 1021
// Author: Tanky Woo
#include 
using namespace std;
int main()
{
    int n;
    while(scanf("%d", &n) != EOF)
    {
        if(n % 8 == 2 || n % 8 == 6)
            printf("yes\n");
        else
            printf("no\n");
    }
    return 0;
}