最大公约数 |漫画算法
一行代码求两个数的最大公约数
http://www.nowcoder.com/questionTerminal/731b967dcda845669fee8c41f0b16e8b
- 辗转相除法:取模运算性能较差，时间复杂度近似为O(log(max(a,b)))
- 更相减损术：算法性能不稳定，最坏为O(max(a,b))
- 更相减损术与移位相结合：性能稳定，时间复杂度为O(log(max(a,b)))
def gcd(a, b): if a == b: return a if a < b : a,b = b,a if a&1 == 0 and b&1 == 0: return gcd(a>>1,b>>1) <<1 elif a&1 == 0 and b&1 != 0: return gcd(a>>1,b) elif a&1 != 0 and b&1 == 0: return gcd(a,b>>1) else: return gcd(b, a-b) m, n = map(int, input().split()) print(gcd(m, n))
