这里给出非递归的 exgcd 做法
【基础】
( 只需要非递归的同学麻烦跳过 )
由于欧几里德算法 ( 又名辗转相除法 ) 可以帮助我们求出最大公约数，并且提出对于
\(\forall a,b\in Z_+,gcd(a,b)|c\) 则 $ ax+by=c $ 一定有整数解
因此，在 \(gcd\) 的基础上，我们提出可以求解 \(x,y\) 的算法：拓展欧几里德算法(exgcd)
如果我们要求解 \(ax+by=gcd(a,b)\)
我们可以知道 \(gcd(a,b)=gcd(b,a\%b)\)
而还有 \(gcd(b,a\%b)=bx'+(a\%b)y'\)
所以，很快可以得到：\(ax+by=bx'+(a\%b)y'\)
\(\because\) 很显然 \(a\%b=a-\lfloor{a\over b}\rfloor\times b\)
\(\therefore\) 我们把上式打开可得到：
\(\qquad ax+by=bx'+ay'-\lfloor{a\over b}\rfloor\times by'\)
\(\qquad ax+by=ay'+b(x'-\lfloor{a\over b}\rfloor y')\)
因此，我们要求得 \(x,y\) 就要先求出 \(x',y'\)
而对于 \(ax+0y=gcd(a,0)=a\) ，显然有解为 \(x=1,y=0\)
这就是递归边界
因此，我们可以写出求 \(x,y\) 的程序：
void exgcd(int a,int b,int &x,int &y){
if(!b) { x=1; y=0; return ; }
exgcd(b,a%b,x,y);
x-=a/b*y;
swap(x,y);
}
那这根这一题有什么关系呢？
你想想，我们要求 \(ax\equiv1(\mod b)\)
是不是相当于求 \(ax=1+by\)
即 \(ax+b(-y)=1\) ?
看到了吗，exgcd 出现了！
所以就是再加一句
inline int ny(int a,int b){
int x,y;
exgcd(a,b,x,y);
x=(x%b+b)%b;
return x;
}
【分析】
这边讲一下如何非递归的实现 exgcd ：
有一部分原理麻烦看一下 这篇文章
已知我们只是需要每次出现的 \(a/b\) 这个值，而且要后面出现的先算，所以我们就把它们压到一个栈里面
算的时候再弹出来就可以了：
int a=read(),b=read(),m=b,tmp[10000]={0},cur=1,x=1,y=0;
tmp[0]=a/b;
while(b^=a^=b^=a%=b) tmp[cur++]=a/b;
while(cur--) y^=x^=y^=x-=tmp[cur]*y;
x=(x%m+m)%m;
【代码】
核心代码我已经放在上面了，现在放出来的是本蒟蒻 码风极丑的 代码：
#include<cstdio>
using namespace std;
inline int read(){
register int ans=0;register char c=getchar(); while(c<48||c>57) c=getchar();
while(c>=48&&c<=57) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
return ans;
}
int main(){
register int a=read(),b=read(),m=b,tmp[10000]={0},cur=1,x=1,y=0; tmp[0]=a/b;
while(b^=a^=b^=a%=b) tmp[cur++]=a/b;
while(cur--) y^=x^=y^=x-=tmp[cur]*y; x%=m;
printf("%d",(x<0)?(x+m):x);
return 0;
}
最后安利一下 本蒟蒻的博客