You need to enable JavaScript to run this app. 扩展欧几里得算法求解ax+by=c 1e18量级计算失效问题
优惠活动
大模型
产品
解决方案
定价
更多

扩展欧几里得算法求解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值。
  • 边界场景兜底缺失
    原代码仅将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

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.10.31 09:06:03