题解 | #求最小公倍数#

求最小公倍数

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

coding=utf-8

''' 原思路: 互余,从乘积,求大余。求小于,求偶数余,求奇数余 --实测15ms ''' try: nn = [int(i) for i in raw_input().split()] a = nn[0] b = nn[1]

max_ji = a * b
tmp = max_ji
last_ji = tmp
min_i = min(a, b)
max_i = max(a, b)

if max_i % min_i == 0:
    print max_i
    exit()
last_ji = max_ji
while True:
    tmp /= max_i
    if tmp % a == 0 and tmp % b == 0:
        last_ji = tmp
    else:    
        break
tmp = last_ji
while True:
    tmp /= min_i
    if tmp % a == 0 and tmp % b == 0:
        last_ji = tmp
    else:    
        break
tmp = last_ji
while True:
    if tmp % 2 == 0:
        tmp /= 2
        if tmp % a == 0 and tmp % b == 0:
            last_ji = tmp
        else:    
            break
    else:
        break
tmp = last_ji
ss = int(last_ji ** 0.5)
for i in range(3, ss + 2, 2):
    tmp = last_ji
    while True:
        if tmp % i == 0:
            tmp /= i
            if tmp % a == 0 and tmp % b == 0:
                last_ji = tmp
            else:    
                break
        else:
            break

print last_ji

except BaseException as e:

print e

pass

''' 分享里的思路: 思路: 有个数a,b的最小公倍数c 假设a<b,那么c肯定是a的倍数; --思路清晰,但是运行时长31ms 补充1,b % a==0,则返回b, 补充2: i从b/a开始 '''

nn = [int(i) for i in raw_input().split()]

a = nn[0]

b = nn[1]

min_i = min(a, b)

max_i = max(a, b)

if max_i % min_i == 0:

print max_i

exit()

cycle = int(max_i / min_i) + 1

while True:

if (min_i * cycle) % max_i == 0:

print min_i * cycle

break

else:

cycle += 1

全部评论

相关推荐

杨柳哥:这不是普通人,那这个钱的是天才
点赞 评论 收藏
分享
孤寡孤寡的牛牛很热情:为什么我2本9硕投了很多,都是简历或者挂,难道那个恶心人的测评真的得认真做吗
点赞 评论 收藏
分享
服从性笔试吗,发这么多笔,现在还在发。
蟑螂恶霸zZ:傻 x 公司,发两次笔试,两次部门匹配挂,
投递金山WPS等公司10个岗位 >
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务