瞎扯 ExGCD用于求解不定方程 ax+by=c 的一组特解。常用于求解同余方程，比如求模非质数意义下的逆元。 推导 主体 首先，不定方程有解的充分必要条件由裴蜀定理给出 gcd(a,b)|c 于是，我们只需关注 ax+by=gcd(a,b) 的解。（原方程的解只需分别对x，y乘上cgcd(a,b)即可求出） （下文中%代指取模操作） 考虑递归的求解。假设我们已经知道了不定方程 bx+(a%b)y=gcd(b,a%b) 的解x1，y1，即 bx1+(a%b)y1=gcd(b,a%b) 现在尝试利用此式构造出原方程的解x，y。 由 gcd(a,b)=gcd(b,a%b) 以及 a%b=a−⌊ab⌋b 原式化为 bx1+(a−⌊ab⌋b)y1=gcd(a,b) 拆开括号 bx1+ay1−⌊ab⌋by1=gcd(a,b) 我们的目标是构造出系数为a，b的原方程，故整理得 ay1+b(x1−⌊ab⌋y1)=gcd(a,b) 成功构造。故 xy=y1=x1−⌊ab⌋y1 该递归的边界条件同欧几里得算法，当b|a时，方程为 ax+by=gcd(a,b)=b x=0，y=1即该方程的一组特解。 构造最小x的特解 Exgcd常用于逆元求解。这时需要找到一组解，使得x最小（正整数范围内）。可以这样构造。 我们知道，不定方程的通解形式为 {xy=x0+kb=y0−ka 所以，以x为例，最小的正整数x=(x0%b+b)%b，然后将其带入不定方程解出y=c−a∗xb即可。 Code namespace ExGcd{ ll x,y; ll ExGcd(ll a,ll b){ ll ans; if(a%b==0){ x=0;y=1;ans=b; }else{ ans=ExGcd(b,a%b); ll x1=x,y1=y; x=y1;y=x1-a/b*y1; } return ans; } bool SolveEqu(ll a,ll b,ll c){ ll d=ExGcd(a,b); if(c%d!=0) return 0; x*=c/d;y*=c/d; //以下为求最小的x x=(x%b+b)%b; y=(c-a*x)/b; return 1; } } //以下为求逆元 ll Inv(ll a,ll m){ ExGcd::SolveEqu(a,m,1); return ExGcd::x; } 板题：洛谷P1082 同余方程，随便改改上面的程序即可。 好文要顶 关注我 收藏该文 sun123zxy 关注 - 7 粉丝 - 1 +加关注 0 0 « 上一篇： bsoj5988 [Achen模拟赛]期望 题解 posted @ 2019-12-21 09:13 sun123zxy 阅读(17) 评论(0) 编辑 收藏 刷新评论刷新页面返回顶部 注册用户登录后才能发表评论，请 登录 或 注册， 访问 网站首页。 【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库 【推荐】腾讯云热门云产品限时秒杀，爆款1核2G云服务器99元/年！ 【推荐】阿里云双11返场来袭，热门产品低至一折等你来抢！ 【活动】京东云服务器_云主机低于1折，低价高性能产品备战双11 【活动】ECUG For Future 技术者的年度盛会（杭州，1月4-5日）https://www.cnblogs.com/sun123zxy/p/exgcd.html