洛谷3986

数学题；

复习了一下拓展欧几里得；ax+by=k;这题中，x,y即为斐波那契中的相邻两项；

问不同的a,b有多少种，显然可以用公式算；而且不重不漏；因为每组的解肯定互不相同；

跨组也没有相同的，因为你认为他们有相同的（a,b）的话，相当于认为（x1,y1）(x2,y2)其中（x2>x1,y2>y1）都是ax+by=k的解；

这显然是不可能的；

#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int p=1e9+7;
ll x,y,f[100],cnt,ans,k;
void exgcd(ll a,ll b,ll &x,ll &y){
    if(!b){x=1;y=0;return;}
    exgcd(b,a%b,y,x);
    y-=x*(a/b);
}
int main(){
    f[1]=1;f[2]=1;
    cnt=2;
    while(f[cnt]<=1e9){
        ++cnt;
        f[cnt]=f[cnt-1]+f[cnt-2];
    }
    cin>>k;
    for(int s=1;s<cnt;++s){
        if(f[s]+f[s+1]>k)break;
        exgcd(f[s],f[s+1],x,y);
        x*=k;y*=k;
        x=((x%f[s+1])+f[s+1])%f[s+1];
        if(!x)x=f[s+1];
        y=(k-f[s]*x)/f[s+1];
        if(y<=f[s]){
            if(y>0)ans=(ans+1)%p;
            continue;
        }
        else{ans=(ans+(y-1)/f[s]+1)%p;}
    }
    cout<<ans<<endl;
    return 0;
}