trick：伪素数 / D3-C pow

ty_mxzhn · 2025-02-11 15:31:00 · 算法·理论

例题：在序列上选出两个不交的区间，使得这两个区间的乘积是完全 k 次方数。求方案数。

分解每个数以后哈希，时间复杂度 O(n^2+nH)。其中 H 是分解一个 a_i 的复杂度。

多提一嘴，我们建议使用的哈希函数是 \sum w(p_i) 而非多项式，前者冲撞率 \dfrac{1}{L}，后者 \dfrac{\log V}{L}。

算法 2

考虑使用伪素数集合 \mathcal{P}，这个集合保证两两互质且可以唯一分解这个序列里的数。

增量构造 \mathcal{P}。每次新增一个数的时候提取其 \gcd 并维护伪素数集合的性质，时间复杂度 O(n^2)。

随后使用伪素数做算法 1，时间复杂度 O(n^2\log V+n\log^2 n)。

补充

本题的伪素数一定不能是一个完全 w 次方数，其中 w\ge 2。留给读者思考。

关于复杂度：

考虑 \displaystyle \sum_{i\in \mathcal{P}} \log i=\log \prod_{i\in \mathcal{P}} i=\sum_{i=1}^n \log a_i=O(n\log V)。做 n 次就是 O(n^2\log n)。