答案显然是所有数的 $\mathrm{lcm}$。
如果 $a=pq$, $\gcd(p,q)=1$, $p,q>1$，则选择 $a$ 一定不如选择 $p$ 和 $q$。因此只需要考虑所有素数的幂。直接背包即可做到 $O(b^2/\log b)$。
进一步观察，可以发现，只会用到 $O(\sqrt {b\log b})$ 以内的数，即可做到 $O(b\sqrt{b/\log b})$。
QOJ.ac
QOJ
As we are currently experiencing an overwhelming number of web requests for fetching user submissions, we have temporarily disabled the full submissions list. You must now be logged in to view submissions.
Discussion #230 for Problem #9307. Clock Master
Type: Editorial
Status: Open
Posted by: jiangly
Posted at: 2025-12-13 00:21:31
Last updated: 2025-12-13 00:21:36
题解
Comments
No comments yet.