扩展欧几里得学习笔记
温馨提示：本文推式子比较多，建议跟着文章自己推一推。
扩展欧几里得是什么
扩展欧几里得（exgcd）是一个可以用来求 ax+by=cax+by=cax+by=c（c%gcd(a,b)=0c\%\gcd(a,b)=0c%gcd(a,b)=0，否则无解）的解的算法
求解 ax+by=gcd(a,b)ax+by=\gcd(a,b)ax+by=gcd(a,b)
首先，如果 b=0b=0b=0 的话，gcd(a,b)=a\gcd(a,b)=agcd(a,b)=a，则解为 {x=1y=0\begin{cases}x=1 \\ y=0\end{cases}{x=1y=0
设此方程的解为 {