扩展欧几里得算法求解ax+by=c 1e18量级计算失效问题
1e18级输入下的故障排查思路
- 核心故障本质:64位long long的运算溢出
64位有符号long long的存储上限约为±9.2e18,仅能支持结果不超过该范围的整数运算。当a、b、c达到1e18量级时,代码中多个位置的计算结果会突破该上限,触发C++定义的未定义整数溢出行为,直接导致结果错乱、程序崩溃:- 扩展欧几里得递归内部的y值更新:原代码执行
y -= x * (a / b)时,x、a/b的取值可达到与a、b同量级(相邻斐波那契数作为输入时,exgcd求出的特解绝对值与输入值相当),二者乘积轻松达到1e36量级,远超long long存储范围。 - 特解缩放计算:原代码执行
x_general = (x + b1) * (c / gcd)时,x与c/gcd的乘积达到1e36量级,直接溢出,无法得到正确的特解。 - y值求解环节:原代码执行
y1 = (c - a * x_min) / b时,a与x_min的乘积同样为1e36量级,溢出后得到的分子值完全随机,无法计算出正确的y值。
- 扩展欧几里得递归内部的y值更新:原代码执行
- 边界场景兜底缺失
原代码仅将a、b、c全为0的输入作为退出条件,未覆盖其他0值输入组合:比如a=0、b非0时的方程合法性校验、b=0时的除0风险判断,容易触发运行时崩溃。
适配大数值输入的优化方案
所有优化不需要引入高精度大数库,仅利用主流编译器(GCC、Clang)原生支持的128位整数类型__int128(存储范围±1.7e38,可完整覆盖两个1e18数相乘的中间运算场景)做过渡即可,核心调整点如下:
- 改造扩展欧几里得递归的更新逻辑,避免中间乘法溢出:
将原递归中y -= x * (a / b)的计算,通过__int128完成中间乘法后再转回long long,写法为y -= (long long)((__int128)x * (a / b)); - 改造特解缩放流程,全程用128位类型避免溢出:
求完ax+by=gcd的特解(x,y)后,计算缩放比例scale = c / gcd,通过__int128完成x的缩放:__int128 scaled_x = (__int128)x * scale;
再基于缩放后的x计算最小非负整数解,全程保留模b/gcd的取模逻辑,写法为long long x_min = (long long)((scaled_x % b1 + b1) % b1); - 改造y值的求解逻辑,通过128位类型计算分子值:
计算y1时,同样用__int128承载a*x_min的乘积,避免溢出,写法为:__int128 numerator = (__int128)c - (__int128)a * x_min;long long y1 = (long long)(numerator / b); - 补全边界场景的合法性判断:
- 若a=0且b=0:仅当c=0时有无穷多解,否则直接输出No Answer,避免除0错误。
- 若a=0:此时方程简化为
by=c,当c能被b整除时,取最小非负解x=0,y=c/b,否则输出No Answer。 - 若b=0:此时方程简化为
ax=c,当c能被a整除时,取最小非负解y=0,x=c/a,否则输出No Answer。
- 可选优化:将递归版exgcd改为迭代实现,由于欧几里得算法的递归深度最多为O(log min(a,b)),1e18量级输入下递归深度仅为几十层,不会触发栈溢出,该调整非必需。
内容的提问来源于stack exchange,提问作者zengzhilin
相关产品推荐
相关产品推荐

