<span>题解 CF1225D</span>
CF1225D：
题意：\(a_i * a_j = x^k\) 求有多少组不同的\((i,j)\)对
很妙的一道hash题/雾
对于原来的柿子：
\(a_i * a_j = x^k\)
我们可以转化成一种什么问题呢？
看到后面的 \(x^k\)你就会想到分解原式，利用唯一分解定理可以得出：
\[a_i = \prod_{i = 1}^{n}{p_i}^{A_i} \]
\[b_i = \prod_{i = 1}^{n}{p_i}^{B_i} \]
\[x = \prod_{i = 1}^{n}{p_i}^{C_i} \]
再看回原来的柿子，可以得到：
\[\prod_{i = 1}^{n}{p_i}^{A_i} * \prod_{i = 1}^{n}{p_i}^{B_i} = \prod_{i = 1}^{n}{p_i}^{C_i^{k}} \]
化简：
\[\prod_{i = 1}^{n}{p_i}^{A_i + B_i} = \prod_{i = 1}^{n}{p_i}^{C_i^{k}} \]
因为对于所有 \(p_i\)都是质数，且对于所有 \(C_i\)都是未定的值，所以只要满足：
\(A_i + B_i = k * t\) 即 \((A_i + B_i) \% k = 0\)
那么这个问题解决了，接下来就是要匹配了，肯定不可以 \(n^2\)暴力
那么就是hash出场了，众所周知 \(hash\) 是个很玄学的东西，你把每个 \(a_i\)分解出来的 \(A_i\) 看出一个字符串，并对它\((A_i)\)和它的互补\(hash\)串\((B_i)\)进行 \(hash\)运算记录下来，并且用神器\(map\)记录每个\(hash\)出现的个数，然后最后只要\(O(n)\)统计一下它的互补\(hash\)串的个数就行了。
查看2道真题和解析