题解 P6659 【[POI 2019] Najmniejsza wspólna wielokrotność】

一只书虫仔 · 2020-08-03 08:05:05 · 题解

P6659 POI 2019 A

Description

给定一个整数 M，求一个区间 [a,b] 使得 M 为这个区间所有数的最小公倍数。
如果有多组解：

• 输出 a 最小的
• 如果还有多组解输出 b 最小的

Solution

注：以下的不会很大为不大于 10^9。

我们可以从区间的大小来考虑最终的区间 [a,b]。

• 如果区间大小为 2，我们考虑到 b 不会很大，所以我们可以使用二分找到区间 [a,b]。
• 如果区间大小为 3，我们可以再次分类得到两个结论：

1. 如果 a 为奇数，M=a(a+1)(a+2)，a 不会很大。
2. 如果 a 为偶数，M=\dfrac{a(a+1)(a+2)}{2}，a 不会很大。

所以我们可以二分找到 a。

• 如果区间大小超过 3 个数，我们可以直接枚举区间，因为我们已知 M 的大小不会超过 10^{18}，所以我们只需要在枚举的过程中看 [a,b] 的 \rm lcm 超没超过 10^{18} 即可。

根据 std 可知，可以用 map 存储。