D.PowerProducts

https://codeforces.com/problemset/problem/1225/D

题目描述

You are given nn positive integers a_1, \ldots, a_na1​,…,an​ , and an integer k \geq 2k≥2 . Count the number of pairs i, ji,j such that 1 \leq i

输入格式

The first line contains two integers nn and kk ( 2 \leq n \leq 10^52≤n≤105 , 2 \leq k \leq 1002≤k≤100 ).

The second line contains nn integers a_1, \ldots, a_na1​,…,an​ ( 1 \leq a_i \leq 10^51≤ai​≤105 ).

输出格式

Print a single integer — the number of suitable pairs.

题意翻译

现在给你nn个正整数 [a_1,a_2,...,a_n][a1​,a2​,...,an​] 和一个的正整数k\geq2k≥2&＃xff0c;现在请你求出有多少组 (i,j)(i,j) &＃xff0c;满足 (1≤i

输入格式

输入第一行是两个正整数nn和kk(2≤n≤10^5,2≤k≤100)(2≤n≤105,2≤k≤100)

第二行为nn个正整数[a_1,a_2,...,a^n](1≤a_i≤10^5)[a1​,a2​,...,an](1≤ai​≤105)

输出格式

输出一个整数&＃xff0c;表示有多少满足条件的组合

样例说明

样例中有以下几组满足条件的组合

a_1*a_4&＃61;8&＃61;2^3a1​∗a4​&＃61;8&＃61;23

a_1*a_6&＃61;1&＃61;1^3a1​∗a6​&＃61;1&＃61;13

a_2*a_3&＃61;27&＃61;3^3a2​∗a3​&＃61;27&＃61;33

a_3*a_5&＃61;216&＃61;6^3a3​∗a5​&＃61;216&＃61;63

a_4*a_6&＃61;8&＃61;2^3a4​∗a6​&＃61;8&＃61;23

一共五组&＃xff0c;所以输出为55

输入输出样例

输入 #1复制

6 3
1 3 9 8 24 1

输出 #1复制

5

说明/提示

In the sample case, the suitable pairs are:

• a_1 \cdot a_4 &＃61; 8 &＃61; 2^3a1​⋅a4​&＃61;8&＃61;23 ;
• a_1 \cdot a_6 &＃61; 1 &＃61; 1^3a1​⋅a6​&＃61;1&＃61;13 ;
• a_2 \cdot a_3 &＃61; 27 &＃61; 3^3a2​⋅a3​&＃61;27&＃61;33 ;
• a_3 \cdot a_5 &＃61; 216 &＃61; 6^3a3​⋅a5​&＃61;216&＃61;63 ;

暴力的思路沿呈https://blog.csdn.net/zstuyyyyccccbbbb/article/details/108357803

式子转化一下可以得到

但是k&＃61;&＃61;2的时候&＃xff0c;预处理的数字个数有1e5个&＃xff0c;然后去处理就超时了。&＃xff08;TLE6&＃xff09;

这题有一个结论&＃xff1a;两个数的积为 k 次方数&＃xff0c;当且仅当每一质因子的次数和都是 k 的倍数。

证明&＃xff1a;把两个数分别个分解质因数了。

A&＃61;p1^k1*p2^k2*p3^k3....pn^kn;

B&＃61;p1^c1*p2^c2*p3^c3.....pn^cn;

对于每个质因数pi,ki&＃43;ci为k的整数倍的时候,i与j成功配对

因为i*j&＃61;p1^(k1&＃43;c1)*p2^(k2&＃43;c2)*.....pt^(kt&＃43;ct)

此时i*j必为X^k.

那么只有k&＃61;&＃61;2TLE&＃xff0c;我们特判k&＃61;&＃61;2的时候。k&＃61;&＃61;2的时候&＃xff0c;也就是i*j的每个质因数pi的次数(ki&＃43;ci)为2的整数倍。也就是只有在ki和ci同时为奇数或者偶数的时候才成立。

那先预处理1e5以内的质因子&＃xff0c;然后对每个a[i]质因数分解&＃xff0c;用bitset维护每个a[i]每个质因数出现的次数。然后把bitset存到unordered_map里&＃xff0c;查询的时候查里面同奇偶的map[bitset]

#include
#include
#include
#include
#include
#include
#include