https://www.luogu.org/problem/P3986
很久很久以前,我好像写过exgcd,但是我已经忘了;
洛谷上搜EXGCD搜不到,要搜(扩展欧几里得)
这道题就是ax+by=k,其中ab为斐波那契数列里面相邻的两项;
a+b=k ;a+2b=k;2a+3b=k,3a+5b=k;
我们求解ax+by=k;
当x最小时,y最大,答案就是y/a向上取整;
因为y=(k-ax)/b;
{设此时的x为x0,则满足x=x0+tb,同理满足y=y0+ta,显然t+1就是此时的答案贡献,
那么用最大的y除以a向上取整即可(注意之所以要向上取整而不是t+1,
是因为避免y=0的情况,还有注意特判x0=0的情况)}(https://www.luogu.org/space/show?uid=24553)
#include<cstring> #include<cstdio> #include<algorithm> using namespace std; typedef long long ll; const int mo=1e9+7; ll f[2000],k; ll x,y; int cnt; void exgcd(ll a,ll b,ll &x,ll &y) { if(!b) { x=1;y=0; return ; } exgcd(b,a%b,y,x); y-=(a/b)*x; } ll ans; int main() { scanf("%lld",&k); f[0]=1;f[1]=1;cnt=2; for(int i=2;i<=100;i++) { f[i]=f[i-1]+f[i-2]; if(f[i]>k) break; ++cnt; } for(int i=1;i<=cnt;i++) { ll a=f[i-1],b=f[i]; exgcd(a,b,x,y); x*=k;//y*=k; x=(x%b+b)%b; if(x==0) x=b; y=(k-a*x)/b; if(y<0) continue; ans=(ans+(y-1)/a+1)%mo; } printf("%lld",ans); return 0; }