自动搬运

查看原文

来自洛谷，原作者为

	小粉兔 Always continue; Never break;

搬运于2025-08-24 21:55:14，当前版本为作者最后更新于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);
}