P3986 斐波那契数列

题目链接

https://www.luogu.com.cn/problem/P3986

分析

列出原始式子

$$\begin{matrix} a + b = k &2\\ a + 2b = k &3\\ 2a + 3b = k &4\\ 3a + 5b = k &5\\ ·\\ ·\\ ·\\ fbi(n-1)\ a+fbi(n)b=k &n \end{matrix}$$

fbi(n) 是下标从 0 开始的斐波那契数列的中下标为 n 的那个数

先考虑某个式子 $ax+by=k$ 的求解

x，y 代表原式中的 f(0),f(1)

a，b代表原式中的系数

由题意可知，我们要求这个方程的正整数解的组数，下面进行求解

1. 无解，由裴蜀定理可知 k%gcd(a,b)!=0 时方程无解

2. 由线性同余方程，可以得出方程通解为

   $$(1)\ x=x_0*\frac{c}{gcd(a,b)}+\frac{b}{gcd(a,b)}t ，y=\frac{c-a*x}{b}\\ (2)\ y=y_0*\frac{c}{gcd(a,b)}-\frac{a}{gcd(a,b)}t ，x=\frac{c-b*y}{a}$$

3. 通过 (1) 可以求出，当 x 取最小非负整数时的解 x1=((x*k/d)%t+t)%t;，由于 x 是正整数，则当 x1=0 时，x1=t 。

4. 通过 (2) 可以求出，当 y 取最小非负整数时的解 ,在对 y 进行正数化后，可以求出 x2 ，易得当 y 取最小值时，x2 取最大值

5. 根据 (1) 的 x 通解公式可以知道，x 的解的数目为 $num=\frac{x_2-x_1}{\frac{b}{gcd(a,b)}}$

对每一个式子进行，求解并总和，即为本题答案。

由于 x>=1,y>=1 则易得 a+b<=k 为边界条件

源码

//分析，在保证方程有解的情况下，ax+by=S，的最小结果是S=gcd(a,b) ,对其进行推广即是本题解法
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
ll ExGcd(ll a,ll b,ll& x,ll& y)
{
	if (b==0)
	{
		x=1;
		y=0;
		return a;
	}
	ll ans=ExGcd(b,a%b,x,y);	//先计算底层x y
	ll temp=y;
	y=x-(a/b)*y;
	x=temp;
	return ans;
}
int main()
{
	ll k,a=1,b=1,c,x,y,d,t,Ans=0;
	cin>>k;
	while(a+b<=k)
	{

		d=ExGcd(a,b,x,y);
		if(k%d==0)//有解
		{
			t=b/d;
			x=((x*k/d)%t+t)%t;
			if(x==0) x+=t;
			y=(k-a*x)/b;//在 x 取最小正整数时，y 取的本题意义上的最大正整数解
			if(y>0)
			{
				Ans+=y/(a/d);
				if(y%(a/d)) Ans++;
				Ans%=mod;
			}
		}
		//斐波那契数列递增
		c=a+b;
		a=b;
		b=c;
	}
	cout<<Ans;
	return 0;
}