题解 | #求最小公倍数#

求最小公倍数

http://www.nowcoder.com/practice/22948c2cad484e0291350abad86136c3

ipt=sys.stdin.read().strip()
ipt=ipt.split(" ")
for i in range(len(ipt)):
    ipt[i]=int(ipt[i])
##输入完毕

##题解:根据集合原理,最小公倍数=ipt[0]*ipt[1]/最大公约数
A=min(ipt)
B=max(ipt)
d=B%A        #余数
if d==0:     #大数可被小数整除,最大公倍数为大数
   print(B)

#注意,B为大数,A为小数,B%A等效于减去最大个数的A
#1:B%A必定小于A
#2:(B与A的最大公约数)与(B%A与A的最大公约数)相同
#此时问题转化为求A与B%A的最大公约数
#依此类推,直到最后的大数可被小数整除,则此时的小数即为最大公约数。
else:
    while d!=0 :    
        B=A
        A=d
        d=B%A
    print(int(ipt[0]*ipt[1]/A))
全部评论

相关推荐

09-29 00:03
门头沟学院 Java
点赞 评论 收藏
分享
10-13 16:58
门头沟学院 Java
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务