如何从满足x=m*A+n*B的序列数组中求解常数A和B？

预处理数组 #

• 先对数组去重，减少冗余计算。
• 计算所有元素的**最大公约数（GCD）**记为d（若数组含0，取非零元素的GCD即可）。将每个元素除以d得到新数组，对应原问题中的A'=A/d、B'=B/d，此时新数组元素是A'和B'的整数线性组合，且所有元素的GCD为1，简化后续计算。

生成差值集合 #

计算数组中所有元素两两之间的差值（忽略0值），得到差值集合D。D中的每个元素都是A'和B'的整数线性组合，等同于A'、B'生成的整数格集合。

分情况求解基（即A'、B'） #

情况1：A、B线性相关（实数域） #

此时所有元素本质是某个数的整数倍。比如B=kA（k为有理数），那么新数组的所有元素都是A'的整数倍，此时A'就是差值集合D的GCD，B'可设为0，或根据k的比值调整（比如k=p/q时，设A'=sq、B'=sp，s为D的GCD）。

情况2：A、B线性无关（实数域） #

此时需要找二维格的一组基：

• 从D中选取绝对值最小的非零元素a（格中最短向量之一）。
• 遍历D中其他元素b，计算b除以a的余数r（满足|r| < |a|/2），找到最小的非零余数r，a和r就是格的一组简化基，对应A'和B'的候选（或它们的线性组合，比如a和a+r也可作为基）。

验证解的有效性 #

得到候选A、B后，需逐一验证数组中每个元素都能表示为mA + nB，其中m、n是(-1000, 1000)范围内的整数。若有元素无法满足，需更换基重新尝试。

关于无解的说明 #

你提到的“问题可能无解”是准确的，常见场景包括：

• 数组元素过少（比如仅1个元素），无法确定A、B的组合，存在无穷多解。
• 数组元素全部落在同一直线上，但原问题假设A、B线性无关，此时无法找到符合条件的二维基。
• 即使元素足够多，解也不唯一——因为整数格的基不唯一，多组(A,B)都能生成相同的元素集合。

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