求解整数解方程y*8.57E-7=x的高效方法问询

问题概述 #

给定方程 y * 8.57E-7 = x，需满足以下约束：

• x > 0
• x 为整数
• y 为整数

此前尝试的方法均遇瓶颈：

• 动态规划缺乏分析思路，无法落地
• 暴力枚举耗时极长且无明确解范围，代码如下（未找到解）：

for x in range(1, 1000000000):
    y = int(1 / (x * 8.57E-7))
    if x * y * 8.57E-7 == 1:
        print(f"{x=}, {y=}")

• Excel规划求解无法添加整数约束

需求：获取此类整数约束方程的快速求解方法、通用思路，以便应对同类问题。

核心解法：数论转化与推导 #

步骤1：消除浮点数，转化为整数方程 #

8.57E-7 本质是分数 857/1000000000，将原方程改写为整数形式：
y * 857 = x * 1000000000

步骤2：数论分析缩小解范围 #

通过质数判定可知857是质数，因此 x * 1000000000 必须能被857整除。由于1000000000与857互质（无共同因子），所以x必须包含857这个因子。

设 x = 857k（k为正整数），代入方程可得：
y * 857 = 857k * 1000000000
约去857后得到：y = 1000000000k

最终通解 #

所有满足条件的解为：

• x = 857k
• y = 1000000000k，其中k为任意正整数

暴力法失败的原因 #

1. 浮点数精度误差：8.57E-7是近似值，浮点数无法精确表示857/1000000000，导致x * y * 8.57E-7 == 1的判断几乎永远不成立。
2. 方程变形错误：原方程是y*8.57E-7 = x，你错误变形为x*y*8.57E-7 ==1，正确的y计算应为y = x / 8.57E-7。

通用求解思路 #

针对这类整数约束下的线性方程问题，最优路径是：

1. 消去浮点数：将方程转化为整数等式或分数形式，避免精度干扰。
2. 数论推导：利用整除、质数分解、最大公约数（GCD）等知识，直接推导解的通式，而非盲目枚举。
3. 工具辅助：复杂场景可借助符号计算库（如Python的SymPy）自动推导，示例代码：

import sympy as sp

# 验证857是否为质数
print(sp.isprime(857))  # 输出True

# 定义变量求解整数解
x, y, k = sp.symbols('x y k', integer=True, positive=True)
eq = sp.Eq(y * 857, x * 10**9)
solutions = sp.solve(eq, (x, y), dict=True)
print(solutions)  # 输出[{x: 857*k, y: 1000000000*k}]

4. 启发式算法的适用边界：启发式算法（遗传、模拟退火等）更适合多约束、非线性、无精确解的优化问题，此类有明确整数解的问题，数论分析效率远高于启发式方法。

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