题解 | #求最小公倍数#

求最小公倍数

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

全部评论

相关推荐

不愿透露姓名的神秘牛友
昨天 17:30
点赞 评论 收藏
分享
lllllkin:感觉可以精简到一页简历,有些排版感觉不是必须的。 时间线越早的,你自己越熟悉的放前面。描述可以更精简些,一些问题解决感觉可以不用写具体技术栈,卖个关子,等面试官问。
点赞 评论 收藏
分享
nus2201602...:兄弟,你这个简历撕了丢了吧,就是一坨,去找几个项目,理解项目流程,看几遍就是你的了,看看八股就去干了,多看看牛客里别人发出来的简历,对着写,你这写的啥啊,纯一坨
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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