描述输入两个正整数 m 和 n 输入它们的最大公约数。输入描述一行两个正整数 m 和 n 之间用空格隔开。输出描述一行一个正整数表示 m 和 n 的最大公约数。用例输入 1 24 36用例输出 1 12提示数据范围:2 = mn = 10000。来源Online Judge http127001cpp
题目要求输入两个正整数m和n,输出它们的最大公约数。
最大公约数(GCD,Greatest Common Divisor)是指能够同时整除两个数的最大正整数。求最大公约数的方法有多种,常见的有辗转相除法和更相减损法。
辗转相除法,也叫欧几里德算法,是通过连续的除法操作,将两个数逐渐缩小为它们的余数,直到余数为0时停止。此时,最后一个非零余数就是最大公约数。
更相减损法则是通过连续的减法操作,将两个数逐渐缩小为它们的差,直到差为0时停止。此时,最后一个非零差就是最大公约数。
以下是使用辗转相除法求最大公约数的示例代码:
def gcd(m, n):
while n != 0:
m, n = n, m % n
return m
m, n = map(int, input().split())
result = gcd(m, n)
print(result)
对于输入示例24和36,经过辗转相除法运算,可以得到最大公约数12。
原文地址: https://www.cveoy.top/t/topic/iOAN 著作权归作者所有。请勿转载和采集!