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,现在请你求出有多少组 (i,j)(i,j) ,满足 (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)
输出格式
输出一个整数,表示有多少满足条件的组合
样例说明
样例中有以下几组满足条件的组合
a_1*a_4=8=2^3a1∗a4=8=23
a_1*a_6=1=1^3a1∗a6=1=13
a_2*a_3=27=3^3a2∗a3=27=33
a_3*a_5=216=6^3a3∗a5=216=63
a_4*a_6=8=2^3a4∗a6=8=23
一共五组,所以输出为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 = 8 = 2^3a1⋅a4=8=23 ;
- a_1 \cdot a_6 = 1 = 1^3a1⋅a6=1=13 ;
- a_2 \cdot a_3 = 27 = 3^3a2⋅a3=27=33 ;
- a_3 \cdot a_5 = 216 = 6^3a3⋅a5=216=63 ;
暴力的思路沿呈https://blog.csdn.net/zstuyyyyccccbbbb/article/details/108357803
式子转化一下可以得到
但是k==2的时候,预处理的数字个数有1e5个,然后去处理就超时了。(TLE6)
这题有一个结论:两个数的积为 k 次方数,当且仅当每一质因子的次数和都是 k 的倍数。
证明:把两个数分别个分解质因数了。
A=p1^k1*p2^k2*p3^k3....pn^kn;
B=p1^c1*p2^c2*p3^c3.....pn^cn;
对于每个质因数pi,ki+ci为k的整数倍的时候,i与j成功配对
因为i*j=p1^(k1+c1)*p2^(k2+c2)*.....pt^(kt+ct)
此时i*j必为X^k.
那么只有k==2TLE,我们特判k==2的时候。k==2的时候,也就是i*j的每个质因数pi的次数(ki+ci)为2的整数倍。也就是只有在ki和ci同时为奇数或者偶数的时候才成立。
那先预处理1e5以内的质因子,然后对每个a[i]质因数分解,用bitset维护每个a[i]每个质因数出现的次数。然后把bitset存到unordered_map里,查询的时候查里面同奇偶的map[bitset]
#include
#include
#include
#include
#include
#include
#include