摘要
Title: 877. 扩展欧几里得算法
Tag: exgcd
Memory Limit: 64 MB
Time Limit: 1000 ms

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)*b)y2$
    $=ay2+bx2-(a/b)*by2;$
    即:$ax1+by1=ay2 + b(x2-(a/b)*y2)$
    根据恒等定理,对应项相等，得:$x1=y2; y1=x2-(a/b)*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)