如何对1e18以内的斐波那契数乘积做最小得分因数分解

问题根源 #

你采用的「优先除以最大斐波那契因数」的贪心算法失效，本质原因是本题定义的斐波那契数之间不互质，会共享质因数。以1008为例，f(11)=144含质因数3，f(7)=21也含质因数3，同时1008含质因数7，必须选至少1个21，优先选144会提前耗尽3，导致21无法被选出，分解失败。

解法1：调整贪心优先级（实现最简单） #

• 第一步：预处理所有≤1e18的斐波那契数，去掉f(1)=1（选1只会额外增加得分，无任何收益），按索引从小到大排列。
• 第二步：对每个斐波那契数，标记它是否包含独有质因数：即该质因数没有出现在所有索引更大的斐波那契数中。
• 第三步：分解时按「独有质因数优先，同优先级从大到小」的顺序遍历斐波那契数，只要当前剩余值能被该斐波那契数整除，就一直除到不能整除为止，记录选的次数。
• 示例验证：1008分解时，21包含独有质因数7，优先级高于144，先除21得到余数48，再处理剩余的斐波那契数就能得到合法分解。

解法2：动态规划（通用性最强，无边界问题） #

如果担心调整贪心优先级依然有遗漏的冲突场景，可以直接用动态规划保证得到最优解：

• 预处理所有≤1e18的斐波那契数，记数组fib，每个元素对应值和索引idx。
• 定义dp[x]为分解数值x能得到的最小得分（暂不减去最后的1），初始状态dp[1] = 0，其余值设为无穷大。
• 从小到大遍历所有可能的x值（或者用记忆化搜索），对每个x遍历所有斐波那契数，如果x % fib[i] == 0，则状态转移：
  dp[x] = min(dp[x], dp[x / fib[i]] + idx[i] + 1)
  （加1是因为新增了一个因数，对应得分里的因数个数计数）
• 最终结果为dp[n] - 1，减去规则要求的「因数个数减1」里的1即可。
• 性能说明：斐波那契数增长极快，≤1e18的斐波那契数仅不到90个，加上n本身是斐波那契数乘积，状态数非常少，运行效率极高。

内容的提问来源于stack exchange，提问作者FeelingGood