P3986 斐波那契数列——数学（EXGCD）

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+;

ll f[],k;

ll x,y;

int cnt;

void exgcd(ll a,ll b,ll &x,ll &y)

{

    if(!b)

    {

        x=;y=;

        return ;

    }

    exgcd(b,a%b,y,x);

    y-=(a/b)*x;

}

ll ans;

int main()

{

    scanf("%lld",&k);

    f[]=;f[]=;cnt=;

    for(int i=;i<=;i++)

    {

        f[i]=f[i-]+f[i-];

        if(f[i]>k) break;

        ++cnt;

    }

    for(int i=;i<=cnt;i++)

    {

        ll a=f[i-],b=f[i];

        exgcd(a,b,x,y);

        x*=k;//y*=k;

        x=(x%b+b)%b;

        if(x==) x=b;

        y=(k-a*x)/b;

        if(y<) continue;

        ans=(ans+(y-)/a+)%mo;

    }

    printf("%lld",ans);

    return ;

}

巴特西

P3986 斐波那契数列——数学（EXGCD）

最新文章

热门文章