求整数n的最小三次方系数十进制表示次数D(n)的高效算法及代码实现方案

先跟大家明确下我们要解决的问题：给定整数n，我们要把它表示成三次方数加权的十进制形式，也就是：
$$n = R_k^3 \times 10^k + R_{k-1}^3 \times 10^{k-1} + \dots + R_0^3$$
这里每个系数$R_i$可以是$-9,-8,\dots,0,\dots,8,9$中的整数。举两个直观例子：

• $37 = 1^3 \times 10 + 3^3$，对应的系数序列是$[1,3]$
• $531$有多种表示，比如$2^3\times102 + (-3)^3\times10 +1^3$（系数序列$[2,-3,1]$），或者更长的序列$[1,-2,-1,-4,-9]$

我们定义的$D(n)$，就是能表示n的这种形式中最小的最高次幂指数（或者说，最短表示序列的长度减1）。比如$D(531)=2$，因为最短的表示用到了$10^2$项，序列长度是3，次数就是2。

现有贪心算法的问题 #

你之前写的d2函数用了贪心思路：每次根据当前数的个位，固定选一个对应的R值，然后迭代计算新的数值。但这种方法有两个致命问题：

1. 贪心不一定得到最优解：每次选的局部最优（比如当前个位对应的某个R）可能导致后续需要更长的序列才能到0
2. 容易陷入循环：没有记录已经处理过的数值，可能会反复进入同一个数值状态，导致无限循环（比如你测试的1002就卡在循环里了）

高效解决方案：广度优先搜索（BFS） #

要找最短路径（这里就是最短的表示次数），BFS是最适合的算法——它会按步数从小到大探索所有可能的路径，一旦找到到0的路径，就是最短的那个。

BFS的核心思路 #

我们可以把每个待处理的数值看成图中的节点，从初始值n出发，每一步对应选择一个合法的R（满足$y \equiv R^3 \pmod{10}$，这样$(y-R^{3)$才能被10整除），然后生成新的节点$y'=(y-R}3)/10$。我们的目标是找到从n到0的最短路径长度（步数），这个步数就是$D(n)$。

具体步骤：

1. 预处理三次方值：先把所有$R \in {-9,...,9}$的$R^{3$和对应的$R}3 \mod10$算出来，方便后续快速匹配
2. 初始化队列和访问记录：队列里存（当前数值，当前步数，系数序列），访问字典记录已经处理过的数值，避免重复计算
3. 迭代处理队列：
   • 取出队列头部的节点
   • 如果当前数值是0，直接返回当前步数和系数序列
   • 如果当前数值已经访问过，跳过
   • 标记当前数值为已访问
   • 找到所有满足$y \equiv R^3 \pmod{10}$的R，计算新的数值$y'=(y-R^3)/10$
   • 将（y', 步数+1, 系数序列+[R]）加入队列
4. 回溯得到结果：因为我们是从n往0走，最后得到的系数序列是逆序的，反转后就是我们需要的$[R_k,...,R_0]$

优化点 #

• 提前筛选合法的R：只保留满足$y \equiv R^3 \pmod{10}$的R，减少不必要的计算
• 记录访问过的数值：避免重复处理同一个状态，防止循环，同时提高效率
• 可以用字典记录每个数值的前驱信息，后续回溯得到最短序列，而不用在队列里存完整序列（节省内存）

代码实现 #

from collections import deque

# 预处理所有R∈{-9,...,9}的三次方值，以及对应的模10结果
cube_map = {}
for r in range(-9, 10):
    cube = r ** 3
    mod10 = cube % 10
    # 统一处理负数模10的情况，确保结果在0-9之间
    if mod10 < 0:
        mod10 += 10
    if mod10 not in cube_map:
        cube_map[mod10] = []
    cube_map[mod10].append((r, cube))

def compute_D(n):
    # 处理负数情况，最后再调整系数符号
    sign = 1
    if n < 0:
        sign = -1
        n = -n
    
    # 队列元素：(当前剩余数值，当前步数，系数列表)
    queue = deque()
    queue.append((n, 0, []))
    # 记录已经访问过的数值，避免循环和重复计算
    visited = set()
    visited.add(n)
    
    while queue:
        current_y, steps, coeffs = queue.popleft()
        
        if current_y == 0:
            # 反转系数列表得到高位到低位的序列，再调整符号
            final_coeffs = [c * sign for c in reversed(coeffs)]
            return steps, final_coeffs
        
        # 计算当前数值的个位模10
        current_mod10 = current_y % 10
        # 找到所有可能的R和对应的R³
        if current_mod10 not in cube_map:
            continue
        for r, cube in cube_map[current_mod10]:
            # 确保(current_y - cube)能被10整除（理论上已经满足，这里做双重校验）
            if (current_y - cube) % 10 != 0:
                continue
            new_y = (current_y - cube) // 10
            if new_y not in visited:
                visited.add(new_y)
                queue.append((new_y, steps + 1, coeffs + [r]))
    
    # 理论上所有整数都能被表示，所以这里不会触发
    return -1, []

# 测试示例
if __name__ == "__main__":
    # 测试531
    d, coeffs = compute_D(531)
    print(f"D(531)={d}, 表示序列：{coeffs}")
    print(f"验证结果：{sum(c**3 * (10**i) for i, c in enumerate(reversed(coeffs)))}")
    
    # 测试之前卡住的1002
    d, coeffs = compute_D(1002)
    print(f"\nD(1002)={d}, 表示序列：{coeffs}")
    print(f"验证结果：{sum(c**3 * (10**i) for i, c in enumerate(reversed(coeffs)))}")
    
    # 批量测试1000-1010
    print("\n批量测试1000-1010：")
    for i in range(1000, 1011):
        d, coeffs = compute_D(i)
        print(f"{i}: D={d}, 序列={coeffs}")

代码说明 #

1. 预处理cube_map：把每个模10值对应的所有（R, R³）对存起来，这样每次可以快速找到当前数值个位对应的合法R
2. BFS队列：用双端队列实现，保证先进先出，确保先处理步数少的节点
3. 访问集合：记录已经处理过的数值，避免循环和重复计算
4. 负数处理：先把n转成正数处理，最后给系数乘上符号，简化逻辑

运行这个代码，之前卡住的1002就能找到最短表示了，而且所有整数都能找到对应的最短次数D(n)。

备注：内容来源于stack exchange，提问作者Pruthviraj