输入 a 和 b , 请返回 a 和 b 的最大公约数。

  • 如果有一个自然数 a 能被自然数 b 整除，则 b 为 a 的约数。2个自然数相同的约数中最大的一个数，为这2个自然数的最大公约数。

更相减损术是出自《九章算术》的一种求最大公约数的算法，它原本是为约分而设计的，但它适用于任何需要求最大公约数的场合。链接-更相减损术

  • 两个数中较大的数能被较小的数整数时，最大公约数为较小数。如果不满足此条件，以较大的数减较小的数，再看差与较小的数是否满足条件；若不满足则继续这个操作，直到满足条件。
# 代码中的类名、方法名、参数名已经指定，直接返回方法规定的值
# 求出a、b的最大公约数。
# @param a int整型 
# @param b int整型 
# @return int整型

class Solution:
    def gcd(self , a: int, b: int) -> int:
        while True:
            c=min(a,b)
            d=max(a,b)
            
            if d%c==0:
                return c
            else:
                a,b=c,d-c