用for循环写辗转相除法

好的，请输入以下代码：

def gcd(a, b):
  while(b):
    a, b = b, a%b
  return a

def extGcd(a, b):
  x, y, u, v = 0, 1, 1, 0
  while(a):
    q, r = divmod(b, a)
    m, n = x-u*q, y-v*q
    b, a, x, y, u, v = a, r, u, v, m, n
  gcd = b
  return gcd, x, y

def inv(a, p):
  gcd, x, y = extGcd(a, p)
  assert(gcd == 1)
  return x%p

a, b = map(int, input().split())
print(gcd(a, b))

输入两个整数，程序将输出它们的最大公约数。

相关问题

用for循环实现辗转相除法

辗转相除法，也称为欧几里得算法，是一种求两个整数最大公约数（GCD）的传统方法。使用for循环实现时，通常会包括以下步骤：

1. 定义两个变量，例如a和b，分别代表需要计算GCD的两个整数。
2. 初始化较小的数作为下一个变量（比如如果a小于b，则将a赋值给c），并将较大的数赋给上一轮的较小数（如果a大于b，则将b赋给c）。
3. 创建一个for循环，条件通常是当c不等于0时继续循环。这是因为一旦c变为0，a就是当前的GCD。
4. 在每次循环内，将原较大的数a除以当前的c，并取余数，把余数赋值给a，原来的c赋值给c。这个过程相当于每次更新较大的数为两数相除后的余数。
5. 循环结束后，a的值就将是两个原始整数的最大公约数。

下面是一个简单的Python示例代码：

def gcd_using_for_loop(a, b):
    while b != 0:
        temp = a % b
        a = b
        b = temp
    return a

# 使用示例
num1 = int(input("请输入第一个整数: "))
num2 = int(input("请输入第二个整数: "))
result = gcd_using_for_loop(num1, num2)
print(f"{num1}和{num2}的最大公约数是: {result}")

用for循环辗转相除法求最大公约数

下面是用for循环实现辗转相除法求最大公约数的代码：

int gcd(int a, int b) {
    int r;
    while (b > 0) {
        r = a % b;
        a = b;
        b = r;
    }
    return a;
}

该函数实现了求a和b的最大公约数。在每次循环中，如果b为0，则说明a就是最大公约数，否则将a赋值为b，将b赋值为a%b的结果，继续循环。