斐波那契数列

本文主要是介绍斐波那契数列，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

• 题意：P3986
• 思路：又先分析题目性质，找规律。发现要求方程：\(f(i)*a+f(i+1)*b=k\)
  然后我们扩欧求出一组解，控制一个变量a为最小正整数，此时用多解公式调整，a只会变大，而b只会变小，然后就求出b的可能即可
• 代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
ll mod=1e9+7,fib[N],k;
ll ex_gcd(ll a,ll b,ll &x,ll &y) {
	if(!b) {x=1,y=0;return b;}
	ll d=ex_gcd(b,a%b,x,y);
	ll t=x;x=y,y=t-(a/b)*y;
	return d;
}
ll gcd(ll a,ll b) {
	if(!b) return a;
	return gcd(b,a%b);
}
int main() {
	ll ans=0;
	scanf("%lld",&k);
	fib[1]=fib[2]=1;
	int c;
	for(c=3;fib[c-1]<=1e9;c++) fib[c]=fib[c-1]+fib[c-2];
	for(int i=2;i<=c;i++) {
		ll a=fib[i-1],b=fib[i],d=gcd(a,b),x0,y0;
		if(k%d) continue; 
		ex_gcd(a,b,x0,y0);
//		printf("%lld %lld\n",x0,y0);
		x0*=k/d,y0*=k/d;
		ll t1=b/d,t2=a/d,t;
		if(x0>0) {
			if(x0%t1==0) t=x0/t1-1;
			else t=x0/t1;
			y0+=t*t2;
		}
		else {
			x0*=-1;
			t=x0/t1+1;
			y0-=t*t2;
		}
		if(y0>0) {
			ans+=y0/t2+1;
			if(y0%t2==0) ans--; 
			ans%=mod;
		}
	}
	printf("%lld",(ans+mod)%mod);
	return 0;
}

这篇关于斐波那契数列的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！