306627: CF1225D. Power Products
Memory Limit:512 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Power Products
题意翻译
现在给你$n$个正整数 $[a_1,a_2,...,a_n]$ 和一个的正整数$k\geq2$,现在请你求出有多少组 $(i,j)$ ,满足 $(1≤i<j≤n)$且存在一个整数 $x$ 满足 $a_i\times a_j=x^k$ ### 输入格式 输入第一行是两个正整数$n$和$k$$(2≤n≤10^5,2≤k≤100)$ 第二行为$n$个正整数$[a_1,a_2,...,a^n](1≤a_i≤10^5)$ ### 输出格式 输出一个整数,表示有多少满足条件的组合 ### 样例说明 样例中有以下几组满足条件的组合 $a_1*a_4=8=2^3$ $a_1*a_6=1=1^3$ $a_2*a_3=27=3^3$ $a_3*a_5=216=6^3$ $a_4*a_6=8=2^3$ 一共五组,所以输出为$5$题目描述
You are given $ n $ positive integers $ a_1, \ldots, a_n $ , and an integer $ k \geq 2 $ . Count the number of pairs $ i, j $ such that $ 1 \leq i < j \leq n $ , and there exists an integer $ x $ such that $ a_i \cdot a_j = x^k $ .输入输出格式
输入格式
The first line contains two integers $ n $ and $ k $ ( $ 2 \leq n \leq 10^5 $ , $ 2 \leq k \leq 100 $ ). The second line contains $ n $ integers $ a_1, \ldots, a_n $ ( $ 1 \leq a_i \leq 10^5 $ ).
输出格式
Print a single integer — the number of suitable pairs.
输入输出样例
输入样例 #1
6 3
1 3 9 8 24 1
输出样例 #1
5