题解：P17733 [ICPC 2019 Xuzhou R] <3 numbers

RiftPhantomsEnderman · 2026-10-22 19:19:51 · 题解

容易发现，质因子数量小于 3 的，只有 1 和质数。

于是问题转化成一个区间内质数数量是否小于总数量的 \frac{1}{3}。

范围太大了，考虑运用估算公式 \frac{n}{\ln(n)}，即质数个数大概是总数量的 \frac{1}{\ln(n)}。

但是这并不是上界，考虑对于较大区间运用此公式而小区间使用暴力判断是否为质数，暴力的时间复杂度为 O(Tn \sqrt{V})，所以设 n 为 60 级别的就行了。

:::info[闲话]{close}

1. 我赛后 n 设成 100000 也过了，非常神奇。

2. 可以用区间筛处理小区间，是 n\ln\ln n 的。