V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
zsh1995
V2EX  ›  算法

腾讯校招的一道题

  •  1
     
  •   zsh1995 · 2018-09-16 20:30:49 +08:00 · 4214 次点击
    这是一个创建于 2020 天前的主题,其中的信息可能已经有所发展或是发生改变。
    `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 多就已经很大了。
    7 条回复    2018-09-17 11:08:50 +08:00
    sylxjtu
        1
    sylxjtu  
       2018-09-16 21:28:08 +08:00 via Android
    对 n 分解质因数,分解成比如 2^a 3^b 5^c 这样,然后对于每一个质因数的幂如 2^a,找到它大于 n 的最小倍数,最后把这些值取一个 max,应该就可以了吧
    sylxjtu
        2
    sylxjtu  
       2018-09-16 21:37:22 +08:00 via Android
    哦,不对,不是分解质因数,是对每个质数找到最高次幂
    ZZZZone
        3
    ZZZZone  
       2018-09-16 23:00:16 +08:00   ❤️ 1
    http://oeis.org/A238898

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

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

    ![]( )
    geelaw
        6
    geelaw  
       2018-09-17 03:05:00 +08:00 via iPhone
    要求 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
        7
    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
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3254 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 14:01 · PVG 22:01 · LAX 07:01 · JFK 10:01
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.