首页 > 代码库 > hdu 1021 斐波那契2,找规律

hdu 1021 斐波那契2,找规律

背景:暴力必定超数据结构范围,因为斐波那契类型数列,成指数形式爆炸增长。故写了数据发现取余30不影响结果。

学习:1.数论类题可以写出几组数据找规律,猜结论。

我的代码:

#include<stdio.h>
int str[1000009] = { 7, 11 };
int main()
{
	int n;
	for (int i = 2; i <=1000000; i++){
		str[i] = (str[i - 1] + str[i - 2])% 30;
	}
	while (scanf("%d", &n) != EOF){
		if (str[n ] % 3 == 0)  printf("yes\n");
		else printf("no\n");
	}
	return 0;
}

也有人根据同余的性质写出递推式{a1≡b1(mod3),得a1+b1(mod3)}:
str[i] = str[i - 1] %3+ str[i - 2]%3;

oms解法:

找规律,一次找出f[0]~f[n]的对三取余的数:

1,2,0,2,2,1,0,1,1,2,0,2,2,1,0,1,1,2,0,2,2,1,0,1.........不断循环

我们的目的是找到取余之后的0与n的关系,除了第一个,0和0之间都是有三个数,所以容易得到只要n%4==2,那么f[n]=0.



hdu 1021 斐波那契2,找规律