極私的極彩色アンサー - TOGENASHI TOGEARI ——from K*(K8)
我怎么每天早上补昨天没写完的鲜花。
算了，放到今天吧。
-
发现 2 开了，和幂次没关系了。
发现有 \(b-a+1\) 个数，猜到是区间。
考虑 \(p\) 和分布位置，可知是质数。
线性筛即可。
9 10. 值域偏大，可以用 Miller_Rabin
-
也是 \(2\) 开，结合 \(+-0\) 和长得像 \(\mu\) 的 \(u\) 是可以猜出是 \(\mu\) 的
线性筛即可。
12 13.
发现值域达到 \(10^{18}\)，考虑快速判 \(\mu\)
\(l\) 指区间长度
首先先筛出 \(10^6\) 以内所有质数，在将区间的数中可以整除的除去，同时记录因数个数 \(O(10^6\log l)\)
考虑 \(10^{18}\) 以内的数最多有 \(2\) 个因数大于 \(10^6\) 次幂，所以剩下的数只可能是：一个质数，一个平方数，一个有两个质因子的数，\(1\)。
我们只需要知道质因子个数，所以可以将其 \(O(1)\) 分类，总复杂度 \(O(l)\)
有点卡常
（因为不会编排数字，干脆摆烂）
标签：10,17,鲜花,18,质数,2024.7,个数,mu From： https://www.cnblogs.com/xrlong/p/18297467