Acwing -- Rank Weekly N0.44

C 合适数对

Link：合适数对

题意：
给定一个长度为$n$的正整数数列 $a1,a2,\dots ,an$ 和一个正整数 $k$。
请你判断共有多少个数对 $(l,r)$ 同时满足：

• $1\le l<r\le n$
• 存在一个整数$x$使得 $a_l?a_r=x^k$成立。

数据范围：
$2\le n\le 10^5$ , $2\le k\le 100$, $1\le a_i\le 10^5$.
输入样例：

6 3
1 3 9 8 24 1

输出样例：

5

分析：
设 满足条件的 $A_i?A_j=N$,将$N$分解质因数：$p_1^{a_1}?p_2^{a_2}?...?p_k^{a_k}$。
其中满足$a_1,a_2,...,a_k$都应是$K$的倍数，这样才能均分给$K$个$X$。
对于一个$A_j$:$p_1^{a_1},p_2^{a_2},...,p_3^{a_k}$(其中$a_1,a_2,...,a_k$是对$K$取模的余数)，我们应找到$A_i:p_1^{K?a_1},p_2^{K?a_2},...,p_3^{K?a_k}$,的个数。
如何快速找到上述$A_i$的个数，哈希，我们可以直接将$A_x$:$p_1^{a_1}?p_2^{a_2}?...?p_3^{a_k}$(其中$a_1,a_2,...,a_k$是对$K$取模的余数)作为哈希关键字，统计个数。

代码：

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;typedef long long LL;
const int N = 1e5 + 10;
int n, k;
int cnt[N];int power(int x, int b)
{
    LL res = 1;while(b --) {
    res *= x;if(res >= N) return 0;}return res;
}int main()
{
    cin >> n >> k;LL ans = 0;while (n -- ){
    int x;cin >> x;LL y = 1, z = 1;//y是x的哈希值，z是与x配对的哈希值。for(int i = 2; i * i <= x; i ++){
    int s = 0;if(x % i == 0)while(x % i == 0) s ++, x /= i;s %= k;y *= power(i, s);z *= power(i, (k - s) % k);}if(x) y *= x, z *= power(x, k - 1);if(z >= N) z = 0;ans += cnt[z];if(y)   cnt[y] ++;}cout << ans << endl;return 0;
}