题目分析

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

关键点：允许使用减法，即可以用 $F_i$ 或 $-F_i$。

核心思路

1. 贪心策略

对于当前的 $n$，找到最接近 $n$ 的斐波那契数 $F$，然后考虑：

• 用加法：$n - F$
• 用减法：$F - n$

选择差值较小的那个方向。

2. 算法流程

1. 预处理：生成所有不超过 $4 \times 10^{17}$ 的斐波那契数
2. 对于每个查询：
   • 当 $n > 0$ 时循环：
     • 找到大于 $n$ 的最小斐波那契数位置 id
     • 计算两种方案的差值：
       • f[id] - n（减法方案）
       • n - f[id-1]（加法方案）
     • 选择较小的差值作为新的 $n$
     • 计数 +1
3. 输出计数结果

代码解析

vector<int> f(2);
f[0] = 1, f[1] = 2;

// 生成斐波那契数列
while (f[f.size() - 1] <= 400000000000000000ll)
    f.pb(f[f.size() - 2] + f[f.size() - 1]);

int t; cin >> t;
while (t--) {
    int ans = 0, n;
    cin >> n;
    
    while (n) {
        ++ans;
        // 二分查找：找到大于n的最小斐波那契数位置
        int id = upper_bound(f.begin(), f.end(), n) - f.begin();
        // 选择差值较小的方向
        n = min(f[id] - n, n - f[id - 1]);
    }
    
    cout << ans << "\n";
}

正确性说明

这种贪心策略的有效性基于斐波那契数列的齐肯多夫定理（Zeckendorf's theorem）的扩展：

• 任何正整数都可以唯一表示为不相邻的斐波那契数之和
• 当允许减法时，可以通过选择最接近的数来快速收敛

复杂度分析

• 预处理：$O(\log M)$，其中 $M = 4 \times 10^{17}$
  • 斐波那契数列呈指数增长，项数很少
• 每次查询：$O(\log k \cdot \log \log k)$
  • 每次迭代至少减少到原来的一半
  • 每次需要 $O(\log \log k)$ 的二分查找

样例验证

输入：

1
1070

处理过程：

1. $n = 1070$，最接近的斐波那契数：
   • $987$（加法：$1070-987=83$）
   • $1597$（减法：$1597-1070=527$） 选择 $83$，计数=1
2. $n = 83$，最接近：
   • $89$（减法：$89-83=6$）
   • $55$（加法：$83-55=28$） 选择 $6$，计数=2
3. $n = 6$，最接近：
   • $5$（加法：$6-5=1$）
   • $8$（减法：$8-6=2$） 选择 $1$，计数=3
4. $n = 1$，直接使用 $1$，计数=4

输出：4

总结

该解法通过贪心+二分巧妙解决了斐波那契表示问题：

• 利用斐波那契数列的指数增长性质
• 每次选择最接近的数，快速收敛
• 时间复杂度优秀，可处理 $10^{17}$ 级别的大数