20251210

说明

本人目前大一上
有很多还不懂
第一次发CSDN
以后想打ACM
请指点 谢谢大佬

题目

已知递推数列的定义如下:
f(0)=7;
f(1)=11;
递推公式: f(n)=f(n-1)+f(n-2);
请解决: 给定一个正整数N(0=<N<=1e18) 需要判定f(N)是否被3整除
如果整除 输出:yes 否则 输出:no

先说输入输出

标准的ACM输入格式
多组数据

#include<iostream>
using namespace std;
int main(){
	int N;
	while(scanf("%d",&N)==1){
		int res=fib_mod(N);
		if(res%3)printf("yes\n");
		else printf("no\n");
	}
}

暴力解法

暴力解法的思路:
先算出f(N) 再判断 f(N)%3

//暴力递归 
int fib_mod(int n){
	if(n==0)return 7;
	if(n==1)return 11;
	return fib_mod(n-1)+fib_mod(n-2); 
}

//暴力非递归
int fib_mod(int n){
	if(n==0)return 7;
	if(n==1)return 11;
	int n1=7;
	int n2=11;
	for(int i=2;i<=n;++i){//就是辗转相加
		int temp=n1+n2;
		n1=n2;
		n2=temp;
	}
	return n2;
} 

暴力解法不能通过 因为N<=1e18 必超时

思路一:发现周期为8

#include<iostream>
#include<vector>
typedef long long ll ;
using namespace std;
//
/*
f(0)=7;		1
f(1)=11;	2
f(2)=18;	0
f(3)=...	2
			2
			1
			0
			1
			//到这里是已经一个周期了  T=8; 
			1
			2
			0
			2
*/

int main(){
	ll N;
	vector<int>arr{1,2,0,2,2,1,0,1};
	while(scanf("%lld",&N)==1){
			int res=arr[N%8];//周期为8 
			printf(res==0?"yes\n":"no\n"); 
	}
	return 0;
}

##思路二:递推模板优化(但是仍然超时)

int fib_mod(long long n){
	int mod=3;
	if(n==0)return 7%mod;
	if(n==1)return 11%mod;
	int n1=7%mod;
	int n2=11%mod;
	for(long long i=2;i<=n;++i){
		int temp=(n1%mod+n2%mod)%mod;
		n1=n2%mod;
		n2=temp;
	}
	return n2;
}
int main(){
	long long  N;
	while(scanf("%dll",&N)==1){
		int res=fib_mod(N);
		printf(res==0?"yes\n":"no\n");
	}
}

好吧 我只会周期法