腾讯校招的一道题

2018-09-16 20:30:49 +08:00
 zsh1995
`LCM`:最小公倍数。<br/>
给定`n`,试求最小的`m`,使得:`LCM( n+1, ... , m) = LCM( 1, ... , m)`。n <= 10^6。<br/>
目前想到的解法是,计算 `LCM( 1, ..., n)` 记为 L, 然后向后找,直到 n+1 到 m 包含了 L 的所有因子。但这样还是要计算 1 到 n 的最小公倍数,这个数在 100 多就已经很大了。
4474 次点击
所在节点    算法
7 条回复
sylxjtu
2018-09-16 21:28:08 +08:00
对 n 分解质因数,分解成比如 2^a 3^b 5^c 这样,然后对于每一个质因数的幂如 2^a,找到它大于 n 的最小倍数,最后把这些值取一个 max,应该就可以了吧
sylxjtu
2018-09-16 21:37:22 +08:00
哦,不对,不是分解质因数,是对每个质数找到最高次幂
ZZZZone
2018-09-16 23:00:16 +08:00
http://oeis.org/A238898

恩。。。 只会打表 OEIS 太弱了
lance6716
2018-09-16 23:04:10 +08:00
@ZZZZone 大佬这玩意怎么搜啊
ZZZZone
2018-09-16 23:17:30 +08:00
@lance6716 写个程序暴力跑出前几项, 然后把数列填上去 search 就行。

主页是这个 http://oeis.org/

![]( )
geelaw
2018-09-17 03:05:00 +08:00
要求 1,...,n 是 lcm(n+1,...,m) 的因数即可。

考虑 lcm(1,...,n) 的标准分解中的每个质数幂 p^k,满足该质数幂的最小的 m 是
p^k * (Floor[n/p^k] + 1)

因此做法是先找到不超过 n 的所有质数,然后升高幂次直到是不超过 n 的最大值。然后计算对应的
p^k * (Floor[n/p^k] + 1)

取其中最大的,就是需要的最小的 m。
wzqcongcong
2018-09-17 11:08:50 +08:00
SetN = {}
for (i = 1 ~ n) {
SetI = i 分解质数
SetN += SetI
}
m = n + 1
while (true) {
SetM = m 分解质数
SetN -= SetM
if (SetN is empty) {
break
}
++m
}
return m

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/489885

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX