Powered by:NEFU AB-IN

Link

877. 扩展欧几里得算法

• 题意

  给定 n 对正整数 ai,bi，对于每对数，求出一组 xi,yi，使其满足 ai×xi+bi×yi=gcd(ai,bi)。

• 思路

  • $b==0$
    $ax+0=gcd(a,0)$
    所以 $x=1,y=0$

  • $b!=0$
    设$ax1+by1=gcd(a,b)$, $bx2+(a\%b)y2=gcd(b,a\%b)$
    由$gcd(a,b)=gcd(b,a\%b)$,可得:
    $ax1+by1=bx2+(a\%b)y2$
    即:$ax1+by1=bx2+(a-(a/b)\ast b)y2$
    $=ay2+bx2-(a/b)\ast by2;$
    即:$ax1+by1=ay2+b(x2-(a/b)\ast y2)$
    根据恒等定理,对应项相等，得:$x1=y2;y1=x2-(a/b)\ast y2$
    这样我们就得到了:$x1$，$y1$的值基于$x2$，$y2$，所以我们可以通过递归求解。

• 代码

  def exgcd(a, b):
      global x, y
      if b == 0:
          x, y = 1, 0
          return a
      
      d = exgcd(b, a % b)
      x, y = y, x
      y -= (a // b) * x
      return d
  
  for _ in range(int(input())):
      a, b = map(int, input().split())
      x, y = 0, 0
      exgcd(a, b)
      print(x, y)