如何最大化乘法操作次数？大t场景下DP内存溢出问题求解

给定两个固定操作：

• operator1：将当前数加x
• operator2：将当前数乘y

从数字1出发，通过顺序执行操作得到目标数t，需满足：

1. 最大化operator2的使用次数
2. 在满足上述条件的前提下，最小化operator1的使用次数

约束条件：1≤x≤1000，2≤y≤1000，1≤t≤10^20。输入为t、x、y，输出operator2的使用次数，无解则返回null。

示例说明 #

• 示例1：输入t=54，x=1，y=3
  输出：3
  解释：通过((1+1)×3³)=54得到目标数，由于3⁴>54，operator2最多可使用3次；因3³≠54，需至少1次operator1。
• 示例2：输入t=3，x=4，y=4
  输出：null
  解释：无法通过加4或乘4从1得到3，故无解。
• 示例3：输入t=2000000000000，x=1，y=2
  输出：40
  解释：2⁴⁰≤2000000000000<2⁴¹，最大化operator2使用次数为40，剩余部分通过operator1补足。

原DP方案的问题 #

原实现使用数组存储每个数值对应的操作次数，当t达到10^20时，数组规模远超内存上限，直接导致OOM，无法运行。

优化思路：反向推导 #

由于t极大，正向遍历所有数值不可行，改为从t反向推导回1，仅处理必要的中间值：

1. 优先执行operator2的反向操作（除以y），以最大化operator2的使用次数；
2. 若当前数无法被y整除，通过数论方法计算需要减去多少次x（operator1的反向操作），使当前数变为可被y整除且≥1的数；
3. 若无法通过上述操作得到合法数值，则检查是否可直接通过减x回到1，否则判定为无解。

核心逻辑 #

• 对于当前数current，若无法被y整除，求解方程k*x ≡ current%y mod y，找到最小非负整数k，使得current -k*x ≥1且能被y整除；
• 若方程无解，检查current-1是否为x的非负整数倍（即能否通过减x直接回到1）；
• 每次成功除以y后，累加operator2的使用次数，直到current变为1或判定无解。

优化后的代码实现 #

import math

def max_multiply(t, x, y):
    if t == 1:
        return 0
    count_op2 = 0
    current = t
    
    while True:
        if current == 1:
            return count_op2
        if current < 1:
            return None
        
        # 处理当前数无法被y整除的情况
        if current % y != 0:
            remainder = current % y
            gcd_val = math.gcd(x, y)
            
            # 检查是否存在合法的k，使得current -k*x 能被y整除且≥1
            if remainder % gcd_val != 0:
                # 无解，检查能否直接减x回到1
                if (current - 1) % x == 0 and (current - 1) >= 0:
                    return count_op2
                else:
                    return None
            else:
                # 求解同余方程，找到最小非负k
                x_div = x // gcd_val
                y_div = y // gcd_val
                rem_div = remainder // gcd_val
                
                # 求x_div在模y_div下的逆元
                try:
                    inv = pow(x_div, -1, y_div)
                except ValueError:
                    return None
                
                k_min = (rem_div * inv) % y_div
                max_possible_k = (current - 1) // x
                
                # 检查最小k是否满足current -k*x ≥1
                if k_min > max_possible_k:
                    # 无合法k，检查能否直接减x回到1
                    if (current - 1) % x == 0 and (current - 1) >= 0:
                        return count_op2
                    else:
                        return None
                
                # 减去k_min次x，得到可被y整除的数
                current -= k_min * x
        
        # 执行反向operator2：除以y
        next_val = current // y
        if next_val < 1:
            # 无法继续除以y，检查能否直接减x回到1
            if (current - 1) % x == 0 and (current - 1) >= 0:
                return count_op2
            else:
                return None
        
        current = next_val
        count_op2 += 1

代码验证 #

• 示例1：max_multiply(54, 1, 3) → 返回3，符合预期；
• 示例2：max_multiply(3, 4, 4) → 返回None，符合预期；
• 示例3：max_multiply(2000000000000, 1, 2) → 返回40，符合预期。

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