유클리드 호제법 (Euclidean Algorithm)

# math.gcd 내장 또는 직접 구현
import math
​
def gcd_recursive(a, b):
  return gcd_recursive(b, a % b) if b else a
​
def gcd_iterative(a, b):
  while b:
      a, b = b, a % b
  return a
​
def extgcd(a, b):
  if b == 0:
      return a, 1, 0
  d, x1, y1 = extgcd(b, a % b)
  x = y1
  y = x1 - (a // b) * y1
  return d, x, y
​
import sys
input = sys.stdin.readline
a, b = map(int, input().split())
print(f"gcd(rec): {gcd_recursive(a, b)}")
print(f"gcd(iter): {gcd_iterative(a, b)}")
print(f"math.gcd: {math.gcd(a, b)}")
d, x, y = extgcd(a, b)
print(f"extgcd: {d}, x={x}, y={y}")
print(f"check: {a}*{x} + {b}*{y} = {a*x + b*y}")

// 재귀 + 반복, BigInteger.gcd() 도 사용 가능
import java.util.*;
import java.io.*;
public class Main {
  static long gcdRecursive(long a, long b) {
      return b == 0 ? a : gcdRecursive(b, a % b);
  }
  static long gcdIterative(long a, long b) {
      while (b != 0) {
          long t = a % b;
          a = b;
          b = t;
      }
      return a;
  }
  static class ExtGcdResult {
      long d, x, y;
      ExtGcdResult(long d, long x, long y) {
          this.d = d; this.x = x; this.y = y;
      }
  }
  static ExtGcdResult extgcd(long a, long b) {
      if (b == 0) return new ExtGcdResult(a, 1, 0);
      ExtGcdResult r = extgcd(b, a % b);
      long x = r.y;
      long y = r.x - (a / b) * r.y;
      return new ExtGcdResult(r.d, x, y);
  }
  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      long a = Long.parseLong(st.nextToken());
      long b = Long.parseLong(st.nextToken());
      System.out.println("gcd(rec): " + gcdRecursive(a, b));
      System.out.println("gcd(iter): " + gcdIterative(a, b));
      ExtGcdResult r = extgcd(a, b);
      System.out.println("extgcd: " + r.d + ", x=" + r.x + ", y=" + r.y);
      System.out.println("check: " + a + "*" + r.x + " + " + b + "*" + r.y + " = " + (a*r.x + b*r.y));
  }
}