1
sylxjtu 2018-09-16 21:28:08 +08:00 via Android
对 n 分解质因数,分解成比如 2^a 3^b 5^c 这样,然后对于每一个质因数的幂如 2^a,找到它大于 n 的最小倍数,最后把这些值取一个 max,应该就可以了吧
|
2
sylxjtu 2018-09-16 21:37:22 +08:00 via Android
哦,不对,不是分解质因数,是对每个质数找到最高次幂
|
3
ZZZZone 2018-09-16 23:00:16 +08:00 1
|
5
ZZZZone 2018-09-16 23:17:30 +08:00
|
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。 |
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 |