这是一个创建于 2777 天前的主题，其中的信息可能已经有所发展或是发生改变。
`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 多就已经很大了。
给定`n`，试求最小的`m`，使得：`LCM( n+1, ... , m) = LCM( 1, ... , m)`。n <= 10^6。<br/>
目前想到的解法是，计算 `LCM( 1, ..., n)` 记为 L， 然后向后找，直到 n+1 到 m 包含了 L 的所有因子。但这样还是要计算 1 到 n 的最小公倍数，这个数在 100 多就已经很大了。
 | 1 sylxjtu 2018 年 9 月 16 日 via Android 对 n 分解质因数，分解成比如 2^a 3^b 5^c 这样，然后对于每一个质因数的幂如 2^a，找到它大于 n 的最小倍数，最后把这些值取一个 max，应该就可以了吧 |
| 2 sylxjtu 2018 年 9 月 16 日 via Android 哦，不对，不是分解质因数，是对每个质数找到最高次幂 |
 | 3 ZZZZone 2018 年 9 月 16 日  1 |
| 5 ZZZZone 2018 年 9 月 16 日 |
) | 6 geelaw 2018 年 9 月 17 日 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。 |
 | 7 wzqcongcong 2018 年 9 月 17 日 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 |
Select Language