自动搬运

查看原文

来自洛谷，原作者为

	我好蒻呀 **

搬运于2025-08-24 21:49:59，当前版本为作者最后更新于2020-02-02 12:36:03，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

给定正整数 $k$，求用斐波那契数的和或差表示 $k$ 所需要的斐波那契数数量最小值。

$k \leq 4\times 10^7$

时空限制：$\texttt{1s/125MB}$

题解界面 LaTeX 渲染可能会有点问题，建议到博客中查看：题解 P3539 【[POI2012]ROZ-Fibonacci Representation】

这题的贪心做法是这样的：每次找到一个离 $k$ 最近的斐波那契数 $F_i$，令 $k\leftarrow|k-F_i|$，重复若干次直到 $k=0$。（即每次令 $k \leftarrow \min|k-F_i|$）

但是我在网上一直找不到比较好的证明，非常自闭QAQ。

首先有几个性质：

• 存在最优方案，不会选择重复的一项。

  证明： 因为我们有 $2F_i=F_{i+1}+F_{i-2}$。

• 存在最优方案，不会选择相邻的两项。

  证明： 通过讨论可以知道

  $+F_i+F_{i+1}=+F_{i+2}$

  $+F_i-F_{i+1}=-F_{i-1}$

  $-F_i+F_{i+1}=+F_{i-1}$

  $-F_i-F_{i+1}=-F_{i+2}$

• 若当前 $F_i \leq k \leq F_{i+1}$，那么存在最优方案，一定包含了 $F_i$ 或 $F_{i+1}$。

  证明： 反证法。假设不包含 $F_i$ 和 $F_{i+1}$。那么根据不选相邻和重复的原则，我们可以证明其他部分的斐波那契数通过加减一定无法凑到 $[F_i,F_{i+1}]$ 内的数。具体地，我们有 $F_{i-1}+F_{i-3}+\cdots<F_i$ 成立，这是因为 $F_1+F_3+\cdots +F_{2n-1}=F_{2n}-1$ 和 $F_2+F_4+\cdots +F_{2n}=F_{2n+1}-1$（为方便设 $F_1=1,F_2=2$）。

  这样一来，$F_1\sim F_{i-1}$ 的数里选出来的和 $S<F_i$。同样我们如果用比 $F_{i+1}$ 大的数拿去减，也会遇到这种的情况： $F_{i+2}-S>F_{i+1}$ ，并且因为不能选相邻的，$F_{i+4}-F_{i+2}>F_{i+3}$ 也是没用的。

  因此我们就证明了，存在最优方案，一定包含了 $F_i$ 或 $F_{i+1}$。

那么接下来，我们就得到了，若当前 $F_{i}\leq k \leq F_{i+1}$，我们一定要从 $F_i,F_{i+1}$ 中选一个。

接下来我们归纳证明，一定是选较近的那个斐波那契数：

• 显然对于满足 $k < F_3$ 的 $k$，结论成立。
• 假设对于满足 $k < F_i$ 的 $k$，结论是成立的，那么接下来考虑证明对于满足 $F_i\leq k<F_{i+1}$ 的 $k$，有结论成立。不妨假设 $k-F_i=a$，$F_{i+1}-k=b$，不失一般性地，设 $a<b$，对于 $a>b$ 同理。
• 接下来证明令 $k\leftarrow a$ 的策略不比 $k \leftarrow b$ 的策略劣。首先有 $a+b=F_{i+1}-F_{i}=F_{i-1}$。根据 $a<b$ 我们有 $b\in (\frac{F_{i-1}}2,F_{i-1}]$，并且因为 $F_{i-3}<\frac{F_{i-1}}{2}<F_{i-2}<F_{i-1}$，而 $\frac{F_{i-1}}2=\frac{F_{i-2}+F_{i-3}}2$，因此离 $b$ 最近的斐波那契数一定是 $F_{i-2},F_{i-1}$ 之一。
• 因为 $b \leq F_{i-1}<F_i$ 满足一定选离 $b$ 较近的斐波那契数，因此我们有 $b$ 的最优表示中一定有 $F_{i-2},F_{i-1}$ 之一。那么 $a=F_{i-1}-b$，所以 $a$ 可以由 $b$ 的表达转化过来，并且 $F_{i-1}$ 可以和 $b$ 的表示中的 $F_{i-2}$ 或是 $F_{i-1}$ 合并/抵消，因此 $a$ 均能得到一种不劣于 $b$ 的表达方式。

至此我们证明了贪心策略的正确性。

显然，$k$ 每次至少减少一半，所以答案是 $\mathcal O(\log k)$ 级别的，这也是时间复杂度的级别。

#include <bits/stdc++.h>

typedef long long s64; 

const s64 lim = 4e17; 

int main()
{
	static s64 f[10001];
	
	int m = 2; 
	f[1] = 1, f[2] = 2; 
	while (f[m] <= lim)
	{
		++m; 
		f[m] = f[m - 2] + f[m - 1]; 
	}

	int orzczk; 
	std::cin >> orzczk; 
	while (orzczk--)
	{
		s64 n; 
		int res = 0; 
		std::cin >> n; 
		while (n)
		{
			++res; 
			int suf = std::upper_bound(f + 1, f + m + 1, n) - f; 
			n = std::min(f[suf] - n, n - f[suf - 1]); 
		}
		std::cout << res << '\n'; 
	}
	return 0; 
}