注意到 N=106N=10^6N=106。普通的 NAiN\sqrt A_iNA i 算法肯定会 T。思考怎么优化。 在 这题 中有个著名的卡常技巧：提前筛出所有的质数，然后枚举时遍历质数就行了。 因为 π(n)≈nln⁡n\pi(n)\approx \frac{n}{\ln n}π(n)≈lnnn ，所以这样就可以把时间复杂度降到 O(NAiln⁡Ai)O(\frac{N\sqrt A_i}{\ln A_i})O(lnAi NA i )。 如果还不放心，想着可能如果有极限数据（如 N,Ai=106N,A_i=10^6N,Ai =106），那么把数组去个重就行了，反正重复的对不同的质因子的贡献没有任何作用。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ @BaiRX运用了神秘方法，使疑似 O(NNlog⁡N)O(N\sqrt N\log N)O(NN logN) 的解法通过了，令人忍俊不禁。

T2 小午的质因子统计 题目大意 求所有数质因数分解后有多少个不同的质因子。 题解思路 可以用埃式筛先预处理出 [1,106][1,10^6][1,106] 所有数的质因子有哪些，然后遍历数组用 setsetset 容器存储所有质因子，因为 setsetset 容器会自动去重，所以最后直接输出 set 容器的 size() 即可。 参考代码

笑点解析：赛时没看数据范围写的然后 AC 顺便首 A 思路 O(n)O(\sqrt{n})O(n ) 直接暴力分解质因数（n14n^{\frac{1}{4}}n41 的 PR 懒得调了），然后使用 set 维护即可。 时间复杂度为 O(∑i=1nailog⁡∑i=1nai)O(\sum_{i=1}^n\sqrt{a_i}\log{\sum_{i=1}^n\sqrt{a_i}})O(∑i=1n ai log∑i=1n ai )（我补刀啊瞎猜的） 代码

O(n)O(\sqrt{n})O(n ) 的质因数分解相信大家人人都会，就不赘述了。 但是 O(nn)O(n\sqrt{n})O(nn ) 在这题会超时，所以我们需要 O(nlog⁡n)O(n \log n)O(nlogn) 计算。 考虑到根号算法耗时在寻找质因子的时候，所以筛法记录每个数的最小质因子。采用埃氏筛。 时间复杂度：O(nlog⁡n)O(n \log n)O(nlogn) 空间复杂度：O(n)O(n)O(n) Code:

N≤106,Ai≤106N\le 10^6,A_i\le 10^6N≤106,Ai ≤106 注意到这个，朴素的 O(nAi)O(nA_i)O(nAi ) 方法肯定不能过。 下意识的想到筛法，于是就打了一个。 便可以优化成 O(nAiln⁡n)O(\frac{nA_i}{\ln n})O(lnnnAi ) 的算法，但这还不够。 注意到：对于一个数 nnn 它最多只有一个大于 n\sqrt nn 的质因子 于是，时间复杂度可以优化成 O(nAiln⁡n)O(\frac{n\sqrt A_i}{\ln n})O(lnnnA i ) 。 最多运行次数在 1e6∗997/6.907≈1.4e81e6*997/6.907\approx 1.4e81e6∗997/6.907≈1.4e8 ,加上判断（剪枝）可以勉强跑过。 code:code:code: