简单的模板题。利用扩展欧几里得即可求。 首先,你要知道在初等数论里,我们把a和b的最大公约数记错记作(a,b),把b可被a整除记作a|b,把b不可被a整除记作a∤b 扩展欧几里得的证明需要用翡蜀定理 对任意的正整数a b,必然存在x y,使得ax+by=(a,b) 若b=0,那么(a,b)=a。此时定理显然成立 若(a,b)!=0,那么将ax+by=(x,y)转换成证bx+(a%b)y=(b,a%b),由欧几里得算法得知该式最终会将b变成0,即变成第一步,得证。 当b=0的时候,我们可以看出x=1,y=0必然是个满足的解,那么我们可以通过反递推得到最终的x,y的值。 那么假设原先x,y值为...