自动搬运

查看原文

来自洛谷，原作者为

	一只书虫仔 End.

搬运于2025-08-24 22:22:51，当前版本为作者最后更新于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 存储。