HDOJ 1021 Fibonacci Again

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](j-i<=9)
3.然后你就可以求出循环t,接下来就是把n对t求余,最后…

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// HDOJ 1021
// Author: Tanky Woo
#include <iostream>
using namespace std;
int main()
{
	int n;
	while(scanf("%d", &amp;n) != EOF)
	{
		if(n % 8 == 2 || n % 8 == 6)
			printf("yes\n");
		else
			printf("no\n");
	}
	return 0;
}

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

《HDOJ 1021 Fibonacci Again》有9个想法

  1. #include
    using namespace std;
    struct Mat{
    int matrix[2][2];
    };
    Mat mat;
    Mat mul(Mat a,Mat b){
    Mat c;
    int i,j,k;
    for(i=0;i<2;i++)
    for(j=0;j<2;j++){
    c.matrix[i][j]=0;
    for(k=0;k<2;k++){
    c.matrix[i][j]+=a.matrix[i][k]*b.matrix[k][j];
    c.matrix[i][j]%=3;
    }
    }
    return c;
    }
    Mat solve(int m){
    Mat c;
    if(m==1)
    return mat;
    else
    if(m&1)
    return mul(solve(m-1),mat);
    else{
    c=solve(m/2);
    return mul(c,c);
    }
    }
    int main(){
    int num;
    Mat tm;
    while(scanf("%d",&num)!=EOF){
    mat.matrix[0][0]=mat.matrix[0][1]=mat.matrix[1][0]=1;
    mat.matrix[1][1]=0;
    if(num==0){
    printf("no\n");
    continue;
    }
    tm=solve(num);
    int sum=tm.matrix[1][0]*7+tm.matrix[1][1]*11;
    if(sum%3==0)
    printf("yes\n");
    else
    printf("no\n");
    }
    return 0;
    }

  2. 除了2104,还有1014也是求互质就行了,我还是想不通。。如果你有时间搞懂了,麻烦你写个帖子行吗?谢了!

  3. 哦~原来这样,我记起了一题类似的,最多是7*7循环,原来是这样推出来的!!谢谢了。可是我的方法我不会证明。。。

    想请教一下2104题,为什么当n和m互质时就符合条件了呢?

  4. 我刚做到这道题,我记得很小的时候老师说过判断一个数能否被3整除,就将这个数的各位的值相加,如果相加的结果能被3整除,则原来的数就能被3整除。对一个任意位的数不断运用这个方法,最终就能化成一个只有个位数的值,我是用这个方法A了,15MS

    #include
    using namespace std;
    int f[1000000];
    int main()
    {
    f[0]=7;
    f[1]=2;
    for(int i=2; i<=1000000; i++)
    {
    f[i]=f[i-1]+f[i-2];
    f[i]=f[i]%10+f[i]/10;
    }
    int n;
    while(scanf("%d",&n)!=EOF)
    {
    if(f[n]%3)
    puts("no");
    else
    puts("yes");
    }
    return 0;
    }

    1. 那个头文件复制时漏了。。忽略它。。
      还有这个结论我没有证明过,可能也不会证。。哈哈哈,只是交流一下。

    2. 汗,为我当年做的这题感到悲哀,这题现在再看一眼,瞬秒~~
      我给你提供这类题的思路吧,我记的有几个和这题类似的。
      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](j-i<=9) 3.然后你就可以求出循环t,接下来就是把n对t求余,最后...

发表评论

电子邮件地址不会被公开。 必填项已用*标注