ax≡1 (mod b) 意思就是说ax 和 1 %b的余数是相等的
1%b就是1
ax%b=1
推出xa-kb=1①
这个式子有一个性质，就是如果这个式子保证成立有解
ab xy 都分别互质
exgcd的一个公式就是
ax+by=gcd(a,b)
①式中的x就是这里的x，-k就是这里的y
ax+by
=gcd(a,b)
=gcd(b,a%b)
=gcd(b,a-(a/b)b)//这里的a/b是整除向下取整
=bx''+(a-(a/b)b)y''
=ay''+(x''-(a/b)y'')b
这里x=y'
y= x''-(a/b)y''