扩展欧几里得算法：
void exgcd(ll a,ll b,ll d,ll&x.ll&y){
if(!b) { d=a,x=1,y=0; }
else { exgcd(b,a%b,d,y,x) ; y-=x*(a/b); }
}迭代法求得方程a*x+b*y=d 使得|x|+|y|最小的x和y，但是x和y不一定是正数，x1=(x+b)%b,y1=(y+a)%a才是满足方程的最小正x和最小正y(但是不一定匹配）
应用：
1.求解不定方程a*x+b*y=d的解
2.求解模的逆元 即求解满足a*x=1(mod b)的x
3,求解同余方程a*x=d(mod b)
京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有