整数？字符串！——Power Products
Sweetlemon
2019-10-29 13:41:00
#### CF #596 Div. 2, D (CF1225D), Power Products
这题非常巧妙，非常值得一做！
两个数的积为 $k$ 次方数，当且仅当每一质因子的次数和都是 $k$ 的倍数。
我们把每一个数的质因数分解的每一个次数都模 $k$，那么同一对里的两个数，一个的次数为 $t$，另一个的次数就必须是 $-t$（$\mod{k}$ 同余意义下）。
首先当然是有一个暴力枚举的思路——枚举数对中靠后的一个数，找它之前有多少可以与它组成“合法数对”（满足上一段所述条件）的数，累加即可。
沿用暴力枚举的思路，如果“找”这一步能用 $O(\log n)$ 的复杂度解决，那么问题就解决了。
如果我们把整数用质因数分解向量形式表示，那么我们也就需要对于一个特定的 $(a_2,a_3,a_5,\cdots)$（指这个数 $2,3,5,\cdots$ 的次数），找到向量 $(-a_2,-a_3,-a_5)$ 的个数。
向量和字符串非常类似（事实上向量 (vector) 就是序列嘛，字符串也不就是 vector<char> 嘛），因此我们可以考虑用字符串的方法来解题。（事实上这句话是赛后总结各种做法的时候才悟出来的。）
从字符串的角度考虑，这就是一个——插入字符串、查询字符串出现次数的问题。
这个问题有两种解法。
一是利用 Trie。当然这题中 Trie 有很多需要调整的地方，比如直接开会 MLE，需要各种分条件优化等（比如把质因子按 $\sqrt{n}$ 分治）。这个可以参考 [$\textcolor{red}{\text{逆流之时}}$](https://www.luogu.org/space/show?uid=144740) 的[题解](https://www.luogu.org/blog/returntime/solution-cf1225d)。
二是利用 Hash（Hana~!）。如果我们能有一种把这些向量准确地 Hash 的方法，就很容易判断是否存在了。
回忆一下哥德尔不完备定理的证明过程，哥德尔是把逻辑公式的字符表示成数，再把数的向量 hash 成自然数的吧？
这个 hash 方法对于一般字符串来说完全不可行，因为 hash 值随随便便就会变得很大。
但我们的向量本来不就是质因数分解向量嘛！这就说明即使把我们的向量用质因数分解方法表示，它也不会很大！
于是，我们的思路就是，对于每一个数，用一个“指数模 $k$ 后的数”来**代表**它。
例如，当 $k=3$ 时，$2^4\times 3^3 \times 7^2 \times 11^1$ 可以用 $2^1\times 3^0 \times 7^2 \times 11^1$ 来代表。
我们每次寻找时只需寻找这个数所需的向量的代表数，如上例中数要配对只需寻找 $2^2\times 3^0 \times 7^1 \times 11^2$ 即可。
接下来似乎就没有问题了。存哈希值用一个 multiset 就可以了吧。
然而……lower_bound 和 upper_bound 之间的距离怎么算呢？
用 std::distance 吧？然而，复杂度：**线性**。
干脆用 multiset::count 吧？复杂度：与容器大小的对数和找到元素的个数成**线性**，也就是说，复杂度是 $O(v+\log n)$ 的，其中 $v$ 指 count 的返回值。
上述两个复杂度的参考资料：
[std::distance](https://zh.cppreference.com/w/cpp/iterator/distance)
> 线性。
> 然而，若 InputIt 额外满足遗留随机访问迭代器 (LegacyRandomAccessIterator) 的要求，则复杂度是常数。
[std::multiset::count](https://zh.cppreference.com/w/cpp/container/multiset/count)
> 与容器大小成对数，加上与找到的元素数成线性。
所以最终我们还是选择了 map……
因此这题有一个额外的价值，那就是科普了上述两个函数的复杂度，尤其是 multiset::count 的诡异复杂度。
附代码。
（我第一次交这篇题解的时候看错题号了……交到了 CF 596D 上去……太丢人了）
```cpp
#include <cstdio>
#include <cctype>
#include <map>
#include <algorithm>
#define MAXIOLG 25
#define FILENAME(x) \
freopen(x".in","r",stdin); \
freopen(x".out","w",stdout);
#define MD(x) (((x)>=MOD)?((x)-=MOD):(0))
#define MAXN 100005
#define N 100000
using namespace std;
typedef long long ll;
typedef long double ld;
typedef ll io_t;
io_t shin[MAXIOLG];
io_t seto(void); //快读
void ayano(io_t x,char spliter='\n'); //快写
int minp[MAXN]={0};
int prime[MAXN],pr=0; //质数筛
int a[MAXN];
int mxdg[MAXN]; //防越界处理,每个数不超过 1e5 的最大次幂
map<ll,int> st;
void make_p(int n); //线性筛
ll kasumi(ll a,ll b);
int main(void){
make_p(100000);
int n,k;
ll ans=0;
n=seto(),k=seto();
for (int i=1;i<=n;i++)
a[i]=seto();
mxdg[1]=0; //无意义
//计算每个数不超过 1e5 的最大幂
for (int i=2;i<=N;i++){
int tans=1;
ll tx=i;
while (tx*i<=N)
tans++,tx*=i;
mxdg[i]=tans;
}
for (int i=1;i<=n;i++){
ll x=a[i]; //当前枚举数列的后一个数为 x
ll y=1; //x 的 hash 为 y
ll u=1; //x 所匹配的 hash 为 u
int uok=1; //防溢出处理, 如果 x 所匹配的数超过了范围则此变量为 0
while (x>1){
int tdeg=0; //此质因数的次数
//质因数分解
int tminp=minp[x];
while (minp[x]==tminp)
x/=tminp,tdeg++;
tdeg%=k; //次数模 k
y*=kasumi(tminp,tdeg); //计算 x 的 hash
int udeg; //x 所匹配的数的此项次数
udeg=(k-tdeg)%k;
if (udeg>mxdg[tminp]) //如果超过了 1e5 的范围
uok=0;
else
u*=kasumi(tminp,udeg);
}
(uok && st.count(u))?(ans+=st[u]):(0); //如果存在 x 所匹配的数, 则累加
//将 x 的 hash 加入 map
if (st.count(y))
st[y]++;
else
st[y]=1;
}
ayano(ans); //输出答案
return 0;
}
void make_p(int n){
//线性筛
int nd2=n>>1;
minp[1]=0;//No meaning
for (int i=2;i<=n;i++){
if (!minp[i]){
minp[i]=i;
prime[pr++]=i;
}
int t;
for (int j=0;j<pr && (t=prime[j]*i)<=n;j++){
minp[t]=prime[j];
if (prime[j]==minp[i])
break;
}
}
}
ll kasumi(ll a,ll b){
//快速幂
ll ans=1;
while (b){
(b&1)?(ans*=a):(0);
a*=a,b>>=1;
}
return ans;
}
io_t seto(void){
//快读
io_t x=0;
char ch=getchar();
int symbol=0;
while (!isdigit(ch))
(ch=='-')?(symbol=1):(0),ch=getchar();
while (isdigit(ch))
x=(x*10)+(ch-'0'),ch=getchar();
return (symbol)?(-x):(x);
}
void ayano(io_t x,char spliter){
//快写
if (!x){
putchar('0'),putchar(spliter);
return;
}
if (x<0)
putchar('-'),x=-x;
int len=0;
while (x){
io_t d=x/10;
shin[len++]=x-d*10;
x=d;
}
while (len--)
putchar(shin[len]+'0');
putchar(spliter);
}
```