题解 P3986 【斐波那契数列】

小粉兔 · 2017-11-27 21:05:58 · 题解

题意：给定 k，求 x+y=k、x+2y=k、2x+3y=k、3x+5y=k、5x+8y=k、……，的正整数解个数。

即要求出关于 x,y 的方程 f_i \cdot x + f_{i+1} \cdot y = k 的正整数解的个数（f_n 是 Fibonacci 数列（斐波那契数列））。

显而易见，当 f_i + f_{i + 1} > k 时，不用继续下去了，因为 a, b 均为正整数，故不同的方程数量有限，可以直接枚举方程。

注意到：

• -5 \cdot 3 + 8 \cdot 2 = 1
• 8 \cdot 5 - 13 \cdot 3 = 1
• -13 \cdot 8 + 21 \cdot 5 = 1
• 21 \cdot 13 - 34 \cdot 8 = 1
• ……

即 f_i f_{i - 1} - f_{i + 1} f_{i - 2} = (-1)^i。
（这里我们定义 f_0 = 0 和 f_{-1} = 1）

所以 f_i \cdot x + f_{i + 1} \cdot y = k 有通解 x = k \cdot (-1)^i f_{i - 1}、y = k \cdot (-1)^{i + 1} f_{i - 2}，根据通解，可以瞎模得出正整数解的个数。

代码：

#include<cstdio>
int n,ans;
long long tx,ty,fx,fy,sx,sy;
int main(){
    scanf("%d",&n);
    for(int p0=1, p1=1, x=0, y=1; p0+p1<=n; p1=p0+p1, p0=p1-p0, x=y-x, y=y-x){
        tx=1ll*x*n, ty=1ll*y*n;
        fx=tx%p1; if(fx<=0) fx+=p1; fy=ty-(fx-tx)/p1*p0;
        sy=ty%p0; if(sy<=0) sy+=p0; sx=tx-(sy-ty)/p0*p1;
        if(fy<=0||sx<=0) break;
        ans=(ans+(sx-fx)/p1+1)%1000000007;
    }
    printf("%d",ans);
}