刷题记录:牛客NC18264斐波那契

传送门:牛客

设f[i]表示斐波那契数论的第i项
f[1]=1,f[2] =1,f[i] = f[i - 1] + f[i - 2]
给定一个n
求f[n-1]*f[n+1]-f[n]^2
1
2
3
4

注意这道题的n十分的大,如果直接做基本上是不可能解出来的,想了一下应该是规律题
如果这是一道数学题,那么我会手算看看有什么规律,但是既然是一道c++题,我选择直接打表寻找一下规律

	f[1]=f[2]=1;
	for(int i=3;i<=10000;i++) {
		f[i]=f[i-1]+f[i-2];
	}
	for(int i=2;i<=100;i++) {
		cout<<f[i-1]*f[i+1]-f[i]*f[i]<<endl;
	}
1
2
3
4
5
6
7

然后发现总是1和-1(根据奇偶的关系)直接的循环,十分的显然,然后根据规律解题即可

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
#define maxn 1000000
int f[10000];
char num[maxn+10];
int main() {
	cin>>num;
	if((num[strlen(num)-1]-'0')%2==1) {
		cout<<"-1"<<endl;
	}else {
		cout<<"1"<<endl;
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34