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$.


-----Input-----

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$).


-----Output-----

Print a single integer — the number of suitable pairs.


-----Example-----
Input
6 3
1 3 9 8 24 1

Output
5



-----Note-----

In the sample case, the suitable pairs are: $a_1 \cdot a_4 = 8 = 2^3$; $a_1 \cdot a_6 = 1 = 1^3$; $a_2 \cdot a_3 = 27 = 3^3$; $a_3 \cdot a_5 = 216 = 6^3$; $a_4 \cdot a_6 = 8 = 2^3$.

Difficulty: MEDIUM_HARD
Tags: Number theory

Mathematics

String algorithms

Starter code:

Solutions:
from collections import defaultdict
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
n = int(max(a) ** 0.5)
mark = [True] * (n + 1)
prime = []
for i in range(2, n + 1):
	if mark[i]:
		for j in range(i, n + 1, i):
			mark[j] = False
		prime.append(i)
d = defaultdict(int)
(ans, count) = (0, 0)
for i in a:
	(t, t1) = ((), ())
	for j in prime:
		if i == 1:
			break
		if i % j == 0:
			count = 0
			while i % j == 0:
				i //= j
				count += 1
			z = count % k
			if z:
				t += (j, z)
				t1 += (j, k - z)
	if i > 1:
		t += (i, 1)
		t1 += (i, k - 1)
	ans += d[t1]
	d[t] += 1
print(ans)


import math
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import math as mt
MAXN = 100001
spf = [0 for i in range(MAXN)]

def sieve():
	spf[1] = 1
	for i in range(2, MAXN):
		spf[i] = i
	for i in range(4, MAXN, 2):
		spf[i] = 2
	for i in range(3, mt.ceil(mt.sqrt(MAXN))):
		if spf[i] == i:
			for j in range(i * i, MAXN, i):
				if spf[j] == j:
					spf[j] = i

def getFactorization(x):
	ret = list()
	while x != 1:
		ret.append(spf[x])
		x = x // spf[x]
	return ret
sieve()
(n, k) = map(int, input().split())
l = list(map(int, input().split()))
d = dict()
ans = 0
for i in range(n):
	s = set()
	rem = set()
	prime = getFactorization(l[i])
	for j in prime:
		if l[i] % j == 0:
			p = 0
			while l[i] % j == 0:
				p += 1
				l[i] //= j
			if p % k != 0:
				s.add(j ** (p % k))
				rem.add(j ** ((k - p) % k))
	s = tuple(s)
	rem = tuple(rem)
	if rem in d:
		ans += d[rem]
	if s in d:
		d[s] += 1
	else:
		d.update({s: 1})
print(ans)


import itertools as it
from collections import defaultdict
import os
import sys

def sieve(n):
	is_prime = [True] * n
	for candidate in it.chain([2], range(3, int(n ** 0.5) + 1, 2)):
		if is_prime[candidate]:
			for k in range(2 * candidate, n, candidate):
				is_prime[k] = False
	primes = [idx for (idx, k) in enumerate(is_prime) if idx >= 2 and k]
	return primes

def factorize(n, primes, k):
	factors = []
	number = n
	for f in primes:
		count = 0
		while number % f == 0:
			count += 1
			number //= f
		if count % k:
			factors.append((f, count % k))
		if f > number:
			break
	if number > 1:
		factors.append((number, 1))
	return tuple(factors)

def solve(arr, k):
	total = 0
	d = defaultdict(int, {})
	primes = sieve(int(100000.0 ** 0.5) + 10)
	for a in arr:
		fac = factorize(a, primes, k)
		fac_complement = tuple(((f, k - count) for (f, count) in fac))
		total += d[fac_complement]
		d[fac] += 1
	return total

def pp(input):
	(n, k) = map(int, input().strip().split())
	arr = map(int, input().strip().split())
	print(solve(arr, k))
if 'paalto' in os.getcwd():
	from string_source import string_source, codeforces_parse
	pp(string_source('6 3\n1 3 9 8 24 1'))
else:
	pp(sys.stdin.readline)


import math

def sieve_of_eratosthenes(n=100000):
	prime = [True for i in range(n + 1)]
	prime[0] = False
	prime[1] = False
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * 2, n + 1, p):
				prime[i] = False
		p += 1
	return prime

def prime_factorization(n, k, prime):
	a = list()
	b = list()
	i = 2
	while n > 1:
		if prime[i]:
			count = 0
			while n % i == 0:
				count += 1
				n = n // i
			if count % k != 0:
				a.append((i, count % k))
				b.append((i, k - count % k))
		i += 1
	return [tuple(a), tuple(b)]

def prime_factorization2(n, k):
	a = list()
	b = list()
	count = 0
	while n % 2 == 0:
		count += 1
		n = n / 2
	if count > 0 and count % k != 0:
		a.append((2, count % k))
		b.append((2, k - count % k))
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		count = 0
		while n % i == 0:
			count += 1
			n = n / i
		if count > 0 and count % k != 0:
			a.append((i, count % k))
			b.append((i, k - count % k))
	if n > 2:
		a.append((n, 1))
		b.append((n, k - 1))
	return [tuple(a), tuple(b)]

def solve(a, k):
	result = 0
	hashmap = {}
	for i in a:
		(x, y) = prime_factorization2(i, k)
		if y in hashmap:
			result += hashmap[y]
		if x in hashmap:
			hashmap[x] += 1
		else:
			hashmap[x] = 1
	return result
values = input().split()
(_, k) = (int(values[0]), int(values[1]))
a = list(map(int, input().split()))
print(solve(a, k))


def f(n):
	Ans = []
	d = 2
	while d * d <= n:
		if n % d == 0:
			Ans.append(d)
			n //= d
		else:
			d += 1
	if n > 1:
		Ans.append(n)
	return Ans
(n, k) = map(int, input().split())
arr = list(map(int, input().split()))
m = {}
c = 0
for i in arr:
	r = {}
	d = 2
	while d * d <= i:
		if i % d == 0:
			r[d] = (r.get(d, 0) + 1) % k
			i //= d
		else:
			d += 1
	if i > 1:
		r[i] = (r.get(i, 0) + 1) % k
	r = tuple(filter(lambda x: x[1], r.items()))
	r2 = tuple(map(lambda x: (x[0], k - x[1]), r))
	c += m.get(r2, 0)
	m[r] = m.get(r, 0) + 1
print(c)


import os, sys
from io import BytesIO, IOBase
from collections import Counter

def main():
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	sieve = [Counter() for _ in range(10 ** 5 + 1)]
	for i in range(2, 10 ** 5 + 1):
		if not len(sieve[i]):
			for x in range(i, 10 ** 5 + 1, i):
				(z, c) = (x, 0)
				while not z % i:
					c += 1
					z //= i
				sieve[x][i] += c
				if sieve[x][i] > k:
					sieve[x][i] %= k
					if not sieve[x][i]:
						sieve[x][i] = k
	x = Counter(a)
	ans = 0
	powe = [pow(2, k)]
	for j in range(3, 400):
		xx = pow(j, k)
		powe.append(xx)
		if xx > 10 ** 5:
			break
	for i in a:
		num = 1
		x[i] -= 1
		for j in sieve[i]:
			num *= pow(j, k - sieve[i][j])
			if num > 10 ** 5:
				break
		ans += x[num]
		for xx in range(2, 400):
			num1 = num * powe[xx - 2]
			if num1 <= 10 ** 5:
				ans += x[num1]
			else:
				break
	print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
d = {}
ans = 0
for el in a:
	i = 2
	a = []
	b = []
	while i * i <= el:
		cnt = 0
		while not el % i:
			el //= i
			cnt += 1
		if cnt % k:
			a.append((i, cnt % k))
			b.append((i, k - cnt % k))
		i += 1
	if el > 1:
		a.append((el, 1))
		b.append((el, k - 1))
	a = tuple(a)
	b = tuple(b)
	ans += d.get(b, 0)
	d[a] = d.get(a, 0) + 1
print(ans)


from math import sqrt

def gd(n, k):
	ans = 1
	obrans = 1
	for i in range(2, int(sqrt(n) + 1)):
		j = 0
		while n % i == 0:
			j += 1
			n //= i
		ans *= pow(i, j % k)
		obrans *= pow(i, -j % k)
	ans *= n
	obrans *= pow(n, k - 1)
	return (ans, obrans)
(n, k) = map(int, input().split())
oba = set()
dct = {}
for i in list(map(int, input().split())):
	(a, b) = gd(i, k)
	dct[a] = dct.get(a, 0) + 1
	(a, b) = (min(a, b), max(a, b))
	oba.add((a, b))
ans = 0
for (i, j) in oba:
	if i == j:
		ans += (dct.get(i, 0) * dct.get(j, 0) - dct.get(i, 0)) // 2
	else:
		ans += dct.get(i, 0) * dct.get(j, 0)
print(ans)


import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')
(n, k) = map(int, input().split())
a = list(map(int, input().split()))

def factors(n, k):
	i = 2
	sq = int(n ** 0.5) + 1
	di = {}
	while n != 1:
		if n % i == 0:
			cur = 0
			while n % i == 0:
				n = n // i
				cur += 1
			if cur % k != 0:
				di[i] = cur % k
		i += 1
		if i > sq:
			break
	if n != 1:
		di[n] = 1
	return '|'.join(('%d:%d' % (i, di[i]) for i in di))
ft = {}
di = {}
for i in a:
	ft[i] = factors(i, k)
	di[ft[i]] = 1 if ft[i] not in di else di[ft[i]] + 1
ans = 0
for i in a:
	ftt = ft[i]
	if ftt == '':
		ans += di[ftt] - 1
	else:
		dx = {}
		for oo in ftt.split('|'):
			(x, y) = map(int, oo.split(':'))
			dx[x] = -y % k
		ftt2 = '|'.join(('%d:%d' % (i, dx[i]) for i in dx))
		if ftt == ftt2:
			ans += di[ftt2] - 1
		elif ftt2 in di:
			ans += di[ftt2]
print(ans // 2)


from collections import defaultdict as dc
dic = dc(lambda : 0)
(x, y) = list(map(int, input().split()))
s = list(map(int, input().split()))
siv = [0] * (max(s) + 1)
ln = len(siv)
siv[1] = 1
for n in range(2, ln):
	if siv[n] == 0:
		siv[n] = n
		for k in range(2 * n, ln, n):
			if siv[k] == 0:
				siv[k] = n

def prf(x):
	dic = dc(lambda : 0)
	while x > 1:
		d = siv[x]
		dic[siv[x]] += 1
		x //= siv[x]
	return dic

def req(dic, k):
	cur = dic
	for n in cur:
		cur[n] %= k
	for n in cur:
		cur[n] = (k - cur[n]) % k
	tot = 1
	for n in cur:
		tot *= n ** cur[n]
	return tot

def conv(x, k):
	dicc = prf(x)
	for n in dicc:
		dicc[n] %= k
	tot = 1
	for n in dicc:
		tot *= n ** dicc[n]
	return tot
res = 0
for n in s:
	re = req(prf(n), y)
	res += dic[re]
	dic[conv(n, y)] += 1
print(res)


import math as mt
from typing import Counter

def sieve():
	spf[1] = 1
	for i in range(2, MAXN):
		spf[i] = i
	for i in range(4, MAXN, 2):
		spf[i] = 2
	for i in range(3, mt.ceil(mt.sqrt(MAXN))):
		if spf[i] == i:
			for j in range(i * i, MAXN, i):
				if spf[j] == j:
					spf[j] = i

def getFactorization(x, k):
	li = dict()
	while x != 1:
		if not spf[x] in li:
			li[spf[x]] = 0
		li[spf[x]] += 1
		if li[spf[x]] == k:
			del li[spf[x]]
		x = x // spf[x]
	li_prime = li.copy()
	for i in li_prime.keys():
		li_prime[i] = k - li_prime[i]
	return (tuple(li.items()), tuple(li_prime.items()))

def Solution(n, k, array):
	lists = dict()
	sieve()
	count = 0
	for i in array:
		if len(mask_li[i]) == 0:
			(li, li_prime) = getFactorization(i, k)
			mask_li[i] = li
			mask_li_prime[i] = li_prime
		if mask_li_prime[i] in lists:
			count += lists[mask_li_prime[i]]
		if mask_li[i] in lists:
			lists[mask_li[i]] += 1
		else:
			lists[mask_li[i]] = 1
	return count
values = input().split()
(n, k) = (int(values[0]), int(values[1]))
a = list(map(int, input().split()))
maximun = max(a)
MAXN = maximun + 1
mask_li = [() for i in range(0, maximun + 1)]
mask_li_prime = [() for i in range(0, maximun + 1)]
spf = [0 for i in range(MAXN)]
result = Solution(n, k, a)
print(result)


import array
import math
import os
import sys

def main():
	init_primes()
	(N, K) = read_ints()
	A = read_ints()
	print(solve(N, K, A))
PRIMES = []
PMAX = 100000

def init_primes():
	b = [0] * (PMAX + 1)
	for i in range(2, PMAX + 1):
		if not b[i]:
			PRIMES.append(i)
			for j in range(i + i, PMAX + 1, i):
				b[j] = 1

def solve(N, K, A):
	high = max(A)
	D = dict()
	for a in A:
		if a not in D:
			D[a] = 0
		D[a] += 1
	ans = 0
	for (a, c) in D.items():
		if a == 1:
			ans += c * (c - 1)
			continue
		b = 1
		x = a
		for p in PRIMES:
			if x == 1:
				break
			if x % p == 0:
				b *= p
				x //= p
				while x % p == 0:
					x //= p
		assert x == 1
		p = b ** K
		i = 1
		while True:
			x = i ** K * p
			if x > high * high:
				break
			if x % a == 0:
				y = x // a
				if a == y:
					ans += c * (c - 1)
				elif y in D:
					f = 1
					if y == 1:
						f = 2
					ans += f * c * D[y]
			i += 1
	return ans // 2
DEBUG = 'DEBUG' in os.environ

def inp():
	return sys.stdin.readline().rstrip()

def read_int():
	return int(inp())

def read_ints():
	return [int(e) for e in inp().split()]

def dprint(*value, sep=' ', end='\n'):
	if DEBUG:
		print(*value, sep=sep, end=end)
main()


from collections import defaultdict
import sys as _sys

def main():
	(n, k) = _read_ints()
	a = tuple(_read_ints())
	result = find_good_pairs_n(a, k)
	print(result)

def _read_line():
	result = _sys.stdin.readline()
	assert result[-1] == '\n'
	return result[:-1]

def _read_ints():
	return map(int, _read_line().split())

def find_good_pairs_n(sequence, k):
	sequence = tuple(sequence)
	factors_seq = tuple(map(_find_prime_factors, sequence))
	factors_seq = map(lambda factors: map(lambda kv: (kv[0], kv[1] % k), factors.items()), factors_seq)
	factors_seq = map(lambda factors: filter(lambda kv: kv[1] > 0, factors), factors_seq)
	factors_seq = map(sorted, factors_seq)
	factors_seq = tuple(map(tuple, factors_seq))
	counter = defaultdict(int)
	for factors in factors_seq:
		counter[factors] += 1
	result = 0
	for factors in factors_seq:
		necessary_factors = tuple(((factor, k - amount) for (factor, amount) in factors))
		result += counter[necessary_factors]
		if factors == necessary_factors:
			result -= 1
	assert result % 2 == 0
	result //= 2
	return result

def _find_prime_factors(x):
	result = dict()
	if x % 2 == 0:
		factor_2_n = 0
		while x & 1 == 0:
			x >>= 1
			factor_2_n += 1
		result[2] = factor_2_n
	factor = 3
	while x != 1 and factor * factor <= x:
		if x % factor == 0:
			factor_n = 0
			while x % factor == 0:
				x //= factor
				factor_n += 1
			result[factor] = factor_n
		factor += 2
	if x != 1:
		result[x] = 1
	return result
main()


(n, mod) = list(map(int, input().split()))
L = list(map(int, input().split()))
m = 10 ** 5 + 2
p = m * [1]
inv = m * [1]
q = m * [0]
for i in range(2, m):
	if q[i] == 0:
		for k in range(i, m, i):
			q[k] = 1
			x = k
			cnt = 0
			while x % i == 0:
				x = x // i
				cnt += 1
			p[k] = p[k] * i ** (cnt % mod)
			if cnt % mod != 0:
				inv[k] = inv[k] * i ** (mod - cnt % mod)
s = {}
tot = 0
for x in L:
	im = inv[x]
	im2 = p[x]
	if im in s:
		tot += s[im]
	if im2 in s:
		s[im2] += 1
	else:
		s[im2] = 1
print(tot)


(n, k) = map(int, input().split())
(*a,) = map(int, input().split())
d = {}
ans = 0
for i in a:
	(x, j, tmp1, tmp2) = (i, 2, [], [])
	while j * j <= i:
		c = 0
		while x % j == 0:
			c += 1
			x //= j
		if c % k:
			tmp2.append((j, k - c % k))
			tmp1.append((j, c % k))
		j += 1
	if x > 1:
		tmp1.append((x, 1))
		tmp2.append((x, k - 1))
	(tmp1, tmp2) = (tuple(tmp1), tuple(tmp2))
	ans += d.get(tmp2, 0)
	d[tmp1] = d.get(tmp1, 0) + 1
print(ans)


import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
import collections
from itertools import permutations
from collections import defaultdict
from collections import deque
import threading
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class SegmentTree:

	def __init__(self, data, default=-10 ** 6, func=lambda a, b: max(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree1:

	def __init__(self, data, default=10 ** 6, func=lambda a, b: min(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)
MOD = 10 ** 9 + 7

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD
mod = 10 ** 9 + 7
omod = 998244353
prime = [True for i in range(50001)]
pp = []

def SieveOfEratosthenes(n=50000):
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	for i in range(50001):
		if prime[i]:
			pp.append(i)
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
n = int(max(a) ** 0.5)
mark = [True] * (n + 1)
primes = []
for i in range(2, n + 1):
	if mark[i]:
		primes.append(i)
		for j in range(i, n + 1, i):
			mark[j] = False
del mark
d = defaultdict(int)
ans = 0
for i in a:
	(t, t1) = ((), ())
	for j in primes:
		if i == 1:
			break
		elif i % j == 0:
			x = 0
			while i % j == 0:
				i //= j
				x += 1
			z = x % k
			if z:
				t += (j, z)
				t1 += (j, k - z)
	if i != 1:
		t += (i, 1)
		t1 += (i, k - 1)
	ans += d[t1]
	d[t] += 1
print(ans)


nmax = 400
eratos = [0 for i in range(nmax + 1)]
prime = []
cnt = 2
while True:
	while cnt <= nmax and eratos[cnt]:
		cnt += 1
	if cnt > nmax:
		break
	eratos[cnt] = 1
	prime.append(cnt)
	for i in range(cnt ** 2, nmax + 1, cnt):
		eratos[i] = 1
from collections import defaultdict
import sys
input = sys.stdin.readline
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
st = set()
for i in prime:
	if i ** k > 10 ** 5:
		break
	st.add(i ** k)
dc = defaultdict(int)
ans = 0
for i in a:
	for j in st:
		while i % j == 0:
			i //= j
	dc[i] += 1
for (i, v) in dc.items():
	x = 1
	y = i
	if i == 1:
		ans += (v - 1) * v // 2
		continue
	if v == 0:
		continue
	for p in prime:
		cnt = 0
		while i % p == 0:
			cnt += 1
			i //= p
		if cnt:
			x *= p ** (k - cnt)
	if i != 1:
		if k == 2:
			x *= i
		else:
			continue
	if x == y:
		ans += v * (v - 1) // 2
		continue
	if x in dc:
		ans += dc[x] * v
		dc[x] = 0
print(ans)


from sys import stdout, stdin, setrecursionlimit
from bisect import insort, bisect_right, bisect_left
from io import BytesIO, IOBase
from collections import *
from itertools import *
from random import *
from string import *
from queue import *
from heapq import *
from math import *
from re import *
from os import *

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = read(self._fd, max(fstat(self._fd).st_size, 8192))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = read(self._fd, max(fstat(self._fd).st_size, 8192))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(stdin, stdout) = (IOWrapper(stdin), IOWrapper(stdout))
(graph, mod, szzz) = ({}, 10 ** 9 + 7, lambda : sorted(zzz()))

def getStr():
	return input()

def getInt():
	return int(input())

def listStr():
	return list(input())

def getStrs():
	return input().split()

def isInt(s):
	return '0' <= s[0] <= '9'

def input():
	return stdin.readline().strip()

def zzz():
	return [int(i) for i in input().split()]

def output(answer, end='\n'):
	stdout.write(str(answer) + end)

def lcd(xnum1, xnum2):
	return xnum1 * xnum2 // gcd(xnum1, xnum2)

def primeNums(N=10 ** 5):
	SN = int(sqrt(N))
	sieve = [i for i in range(N + 1)]
	sieve[1] = 0
	for i in sieve:
		if i > SN:
			break
		if i == 0:
			continue
		for j in range(2 * i, N + 1, i):
			sieve[j] = 0
	prime = [i for i in range(N + 1) if sieve[i] != 0]
	return prime

def primeFactor(n, prime=primeNums()):
	lst = []
	mx = int(sqrt(n)) + 1
	for i in prime:
		if i > mx:
			break
		while n % i == 0:
			lst.append(i)
			n //= i
	if n > 1:
		lst.append(n)
	return lst
dx = [-1, 1, 0, 0, 1, -1, 1, -1]
dy = [0, 0, 1, -1, 1, -1, -1, 1]
daysInMounth = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
(n, k) = zzz()
a = zzz()
d = {}
ans = 0
for i in a:
	(x, j, tmp1, tmp2) = (i, 2, [], [])
	while j * j <= i:
		c = 0
		while x % j == 0:
			c += 1
			x //= j
		if c % k:
			tmp2.append((j, k - c % k))
			tmp1.append((j, c % k))
		j += 1
	if x > 1:
		tmp1.append((x, 1))
		tmp2.append((x, k - 1))
	(tmp1, tmp2) = (tuple(tmp1), tuple(tmp2))
	ans += d.get(tmp2, 0)
	d[tmp1] = d.get(tmp1, 0) + 1
print(ans)


import math

def fac(a):
	ans = {}
	for i in range(2, int(math.sqrt(a)) + 1):
		if a % i == 0:
			ans[i] = 0
			while a % i == 0:
				a //= i
				ans[i] += 1
	ans[a] = 1
	return ans

def inverse(a, k):
	buf = {}
	for j in a.keys():
		buf[j] = (k - a[j] % k) % k
	return buf

def normal(a, k):
	buf = {}
	for j in a.keys():
		buf[j] = a[j] % k
	return buf

def getHash(d):
	ans = 1
	for i in d.keys():
		ans *= i ** d[i]
	return ans
(n, k) = map(int, input().split(' '))
a = [i for i in map(int, input().split(' '))]
b = [i for i in map(fac, a)]
factors = {}
for i in b:
	buf = getHash(inverse(i, k))
	if buf in factors.keys():
		factors[buf] += 1
	else:
		factors[buf] = 1
ans = 0
for i in range(len(b)):
	b[i] = normal(b[i], k)
	if getHash(b[i]) == getHash(inverse(b[i], k)):
		ans -= 1
for i in map(getHash, b):
	if i in factors.keys():
		ans += factors[i]
print(ans // 2)


import collections
import time
import os
import sys
import bisect
import heapq
from typing import List
import math

def factors(val):
	wc = []
	for i in range(2, int(math.sqrt(val)) + 2):
		if i > val:
			break
		if val % i == 0:
			c = 0
			while val % i == 0:
				c += 1
				val //= i
			wc.append((i, c))
	if val > 1:
		wc.append((val, 1))
	return wc

def expand(fc, maxd, k):

	def dfs(index, mul):
		if index >= len(fc):
			return [mul]
		(w, c) = fc[index]
		d = k - c % k if c % k != 0 else 0
		x = []
		t = mul * w ** d
		while t <= maxd:
			x.extend(dfs(index + 1, t))
			d += k
			t *= w ** k
		return x
	return dfs(0, 1)

def solve(N, K, A):
	wc = collections.defaultdict(int)
	ans = 0
	for v in A:
		fc = factors(v)
		fc = [(f, c % K) for (f, c) in fc if c % K != 0]
		key = '_'.join(['{}+{}'.format(f, c) for (f, c) in fc])
		cov = [(f, K - c) for (f, c) in fc]
		ckey = '_'.join(['{}+{}'.format(f, c) for (f, c) in cov])
		ans += wc[ckey]
		wc[key] += 1
	return ans
(N, K) = map(int, input().split())
A = [int(x) for x in input().split()]
print(solve(N, K, A))


from collections import Counter as C
NN = 100000
X = [-1] * (NN + 1)
L = [[] for _ in range(NN + 1)]
k = 2
while k <= NN:
	X[k] = 1
	L[k].append(k)
	for i in range(k * 2, NN + 1, k):
		X[i] = 0
		L[i].append(k)
	d = 2
	while k ** d <= NN:
		for i in range(k ** d, NN + 1, k ** d):
			L[i].append(k)
		d += 1
	while k <= NN and X[k] >= 0:
		k += 1
P = [i for i in range(NN + 1) if X[i] == 1]
K = 4

def free(ct):
	a = 1
	for c in ct:
		a *= c ** (ct[c] % K)
	return a

def inv(ct):
	a = 1
	for c in ct:
		a *= c ** (-ct[c] % K)
	return a
(N, K) = map(int, input().split())
A = [int(a) for a in input().split()]
D = {}
ans = 0
for a in A:
	c = C(L[a])
	invc = inv(c)
	if invc in D:
		ans += D[invc]
	freec = free(c)
	if freec in D:
		D[freec] += 1
	else:
		D[freec] = 1
print(ans)


import math

def prime_factorization(n, k):
	a = list()
	b = list()
	count = 0
	while n % 2 == 0:
		count += 1
		n = n / 2
	if count > 0 and count % k != 0:
		a.append((2, count % k))
		b.append((2, k - count % k))
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		count = 0
		while n % i == 0:
			count += 1
			n = n / i
		if count > 0 and count % k != 0:
			a.append((i, count % k))
			b.append((i, k - count % k))
	if n > 2:
		a.append((n, 1))
		b.append((n, k - 1))
	return [tuple(a), tuple(b)]

def solve(a, k):
	result = 0
	hashmap = {}
	for i in a:
		(x, y) = prime_factorization(i, k)
		if y in hashmap:
			result += hashmap[y]
		if x in hashmap:
			hashmap[x] += 1
		else:
			hashmap[x] = 1
	return result
values = input().split()
(_, k) = (int(values[0]), int(values[1]))
a = list(map(int, input().split()))
print(solve(a, k))


import os
import sys
from io import BytesIO, IOBase
from collections import Counter

def seieve_prime_factorisation(n):
	(p, i) = ([1] * (n + 1), 2)
	while i * i <= n:
		if p[i] == 1:
			for j in range(i * i, n + 1, i):
				p[j] = i
		i += 1
	return p

def prime_factorisation_by_seive(p, x):
	c = Counter()
	while p[x] != 1:
		c[p[x]] += 1
		x = x // p[x]
	c[x] += 1
	return c

def main():
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	ma = max(a)
	p = seieve_prime_factorisation(ma)
	b = Counter()
	(ans, z) = (0, 0)
	for i in a:
		if i != 1:
			(c, d) = ([], [])
			e = prime_factorisation_by_seive(p, i)
			for j in sorted(e.keys()):
				y = e[j] % k
				if y:
					c.append((j, y))
					d.append((j, k - y))
			if c:
				(c, d) = (tuple(c), tuple(d))
				b[c] += 1
				ans += b[d] - (c == d)
			else:
				z += 1
		else:
			z += 1
	print(ans + z * (z - 1) // 2)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import math
from collections import Counter
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
ans = 0
prev = Counter()
for x in a:
	sig = []
	p = 2
	while p <= math.sqrt(x):
		cnt = 0
		while x % p == 0:
			cnt += 1
			x = x // p
		cnt = cnt % k
		if cnt > 0:
			sig.append((p, cnt))
		p += 1
	if x > 1:
		sig.append((x, 1))
	com_sig = []
	for (p, val) in sig:
		com_sig.append((p, (k - val) % k))
	ans += prev[tuple(sig)]
	prev[tuple(com_sig)] += 1
print(ans)


from collections import defaultdict
largerPrime = list(range(10 ** 5 + 1))

def largestPrime(N=10 ** 5):
	for i in range(2, N + 1):
		if largerPrime[i] == i:
			for j in range(i * 2, N + 1, i):
				largerPrime[j] = i
largestPrime()

def primeFactors(n, k):
	primeFactors = defaultdict(int)
	while n != 1:
		primeFactors[largerPrime[n]] += 1
		primeFactors[largerPrime[n]] %= k
		n = int(n / largerPrime[n])
	return primeFactors

def negate(pair, k):
	neg = []
	for key in pair:
		if pair[key]:
			neg.append((key, k - pair[key]))
	neg.sort()
	if neg:
		return neg
	return 1
(n, k) = map(int, input().split())
arr = [int(x) for x in input().split()]
one = 0
ans = 0
d = defaultdict(int)
for i in arr:
	fac = primeFactors(i, k)
	x = negate(fac, k)
	if x == 1:
		ans += one
		one += 1
	else:
		x = tuple(x)
		ans += d[x]
		save = []
		for key in fac:
			if fac[key]:
				save.append((key, fac[key]))
		save.sort()
		d[tuple(save)] += 1
print(ans)


from collections import defaultdict
import math
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
ans = 0
hm = defaultdict(int)
for i in range(n):
	x = 2
	t = []
	t1 = []
	y = a[i]
	while x <= math.sqrt(a[i]):
		if a[i] % x == 0:
			c = 0
			while y % x == 0:
				y = y // x
				c += 1
			if c % k > 0:
				t.append((x, c % k))
				t1.append((x, k - c % k))
		x += 1
	if y > 1:
		t.append((y, 1 % k))
		t1.append((y, k - 1 % k))
	ans += hm[tuple(t1)]
	hm[tuple(t)] += 1
print(ans)


from collections import defaultdict

class Primes:

	def __init__(self, N):
		self.N = N
		self.prime = {i for i in range(2, self.N + 1)}
		self.spf = [-1] * (N + 1)
		for i in range(2, self.N + 1):
			if i in self.prime:
				self.spf[i] = i
				for j in range(i * 2, self.N + 1, i):
					if j in self.prime:
						self.spf[j] = i
						self.prime.remove(j)

	def fact(self, Number):
		v = Number
		d = defaultdict(int)
		while v > 1:
			x = self.spf[v]
			d[x] += 1
			v //= x
		return d
P = Primes(10 ** 5)
(n, k) = list(map(int, input().split()))
a = list(map(int, input().split()))
cnt = [0] * (10 ** 5 + 1)
for v in a:
	cnt[v] += 1
ans = 0
for v in a:
	cnt[v] -= 1
	d = P.fact(v)
	res = 1
	for (num, order) in list(d.items()):
		res *= pow(num, (k - order % k) % k)
	if res <= 10 ** 5:
		for i in range(1, 1000):
			if pow(i, k) * res > 10 ** 5:
				break
			ans += cnt[pow(i, k) * res]
print(ans)


(n, k) = list(map(int, input().split()))
arr = list(map(int, input().split()))
ans = 0
d = {}
for i in range(n):
	x = 2
	a = []
	b = []
	y = arr[i]
	while x * x <= arr[i]:
		if arr[i] % x == 0:
			c = 0
			while y % x == 0:
				y = y // x
				c += 1
			if c % k > 0:
				a.append((x, c % k))
				b.append((x, k - c % k))
		x += 1
	if y > 1:
		a.append((y, 1 % k))
		b.append((y, k - 1 % k))
	try:
		ans += d[tuple(b)]
	except:
		pass
	try:
		d[tuple(a)] += 1
	except:
		d[tuple(a)] = 1
print(ans)


from collections import defaultdict
import sys

class Primes:

	def __init__(self, N):
		self.n = N
		self.spf = [1] * (N + 1)
		self.isprime = [True] * (N + 1)
		self.isprime[0] = self.isprime[1] = False
		self.primes = []
		for i in range(2, N + 1):
			if self.isprime[i]:
				self.primes.append(i)
				self.spf[i] = i
				for j in range(i * i, N + 1, i):
					self.isprime[j] = False
					self.spf[j] = i

	def GETPRIMES(self):
		return self.primes

	def fact(self, M):
		assert M <= self.n
		d = defaultdict(int)
		while M > 1:
			p = self.spf[M]
			exp = 0
			while M % p == 0:
				M //= p
				exp += 1
			d[p] = exp
		return d

	def isprime(self, M):
		assert M <= self.n
		return self.isprime[M]

def input():
	return sys.stdin.readline().rstrip()
MAXN = int(100000.0)

def slv():
	(n, k) = map(int, input().split())
	P = Primes(MAXN)
	Pairs = set([])
	a = list(map(int, input().split()))
	C = [0] * (MAXN + 1)
	for elem in a:
		fac = P.fact(elem)
		v = 1
		pair_v = 1
		for (p, ord) in fac.items():
			if ord % k != 0:
				v *= pow(p, ord % k)
				pair_v *= pow(p, k - ord % k)
		C[v] += 1
		(v, pair_v) = (min(v, pair_v), max(v, pair_v))
		if not (len(fac) > 1 and k > 60):
			Pairs.add((v, pair_v))
	ans = 0
	for (v, pair_v) in Pairs:
		if v <= MAXN and pair_v <= MAXN:
			if v != pair_v:
				ans += C[v] * C[pair_v]
			else:
				ans += C[v] * (C[pair_v] - 1) // 2
	print(ans)
	return

def main():
	t = 1
	for i in range(t):
		slv()
	return
main()


from collections import defaultdict
total = 0
import math
dic = defaultdict(int)
(n, k) = list(map(int, input().split()))
z = list(map(int, input().split()))
for ii in z:
	i = ii
	x = []
	x2 = []
	a = 2
	while a <= math.sqrt(ii):
		co = 0
		while i % a == 0:
			i = i // a
			co += 1
		co = co % k
		if co:
			x.append((a, co))
			x2.append((a, k - co))
		a += 1
	if i > 1:
		x.append((i, 1))
		x2.append((i, k - 1))
	dic[tuple(x)] += 1
	total += dic[tuple(x2)]
	if x2 == x:
		total -= 1
print(total)


(n, k) = map(int, input().split())
A = list(map(int, input().split()))
import math
from collections import Counter
C = Counter()
for x in A:
	L = int(math.sqrt(x))
	FACT = dict()
	for i in range(2, L + 2):
		while x % i == 0:
			FACT[i] = FACT.get(i, 0) + 1
			x = x // i
	if x != 1:
		FACT[x] = FACT.get(x, 0) + 1
	for f in list(FACT):
		FACT[f] %= k
		if FACT[f] == 0:
			del FACT[f]
	if FACT == dict():
		C[1, 1] += 1
	else:
		RET = 1
		ALL = 1
		for f in FACT:
			RET *= f ** FACT[f]
			ALL *= f ** k
		C[RET, ALL // RET] += 1
ANS = 0
ANS2 = 0
for (x, y) in C:
	if x == y:
		ANS += C[x, y] * (C[x, y] - 1) // 2
	else:
		ANS2 += C[x, y] * C[y, x]
print(ANS + ANS2 // 2)


import sys
input = sys.stdin.readline
from collections import defaultdict
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
dd = defaultdict(int)
ans = 0
for aa in a:
	primes = []
	b = aa
	for j in range(2, int(b ** 0.5) + 1):
		if b % j == 0:
			cnt = 0
			while b % j == 0:
				cnt += 1
				b //= j
			primes.append([j, cnt])
	if b > 1:
		primes.append([b, 1])
	(key1, key2) = (1, 1)
	for (p, c) in primes:
		if c % k != 0:
			key1 *= p ** (c % k)
			key2 *= p ** (k - c % k)
	ans += dd[key2]
	dd[key1] += 1
print(ans)


from math import *
(n, k) = list(map(int, input().split()))
a = [int(i) for i in input().split()]
ma = max(a)
p = []
prime = [True] * (ma + 1)
prime[0] = False
prime[1] = False
for i in range(2, ma + 1):
	if prime[i]:
		p.append(i)
		if i ** 2 <= n:
			for j in range(i ** 2, ma + 1, i):
				prime[j] = False

def factor(x):
	res = {}
	sq = ceil(sqrt(x))
	for i in p:
		if i > sq or x <= 1:
			break
		if x % i == 0:
			res[i] = 0
			while x % i == 0:
				res[i] += 1
				x //= i
	if x > 1:
		res[x] = 1
	nres = []
	for j in res:
		if res[j] % k > 0:
			nres.append((j, res[j] % k))
	return tuple(nres)
d = {}
for i in range(n):
	f = factor(a[i])
	if f not in d:
		d[f] = 1
	else:
		d[f] += 1
ans = 0
for x in d:
	y = []
	for i in x:
		y.append((i[0], k - i[1]))
	y = tuple(y)
	if y in d:
		if y != x:
			ans += d[x] * d[y]
		else:
			ans += d[x] * (d[y] - 1)
print(ans // 2)


from collections import defaultdict
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
n = int(max(a) ** 0.5)
mark = [True] * (n + 1)
primes = []
for i in range(2, n + 1):
	if mark[i]:
		primes.append(i)
		for j in range(i, n + 1, i):
			mark[j] = False
d = defaultdict(int)
ans = 0
for i in a:
	(t, t1) = ((), ())
	for j in primes:
		if i == 1:
			break
		elif i % j == 0:
			x = 0
			while i % j == 0:
				i //= j
				x += 1
			z = x % k
			if z:
				t += (j, z)
				t1 += (j, k - z)
	if i != 1:
		t += (i, 1)
		t1 += (i, k - 1)
	ans += d[t1]
	d[t] += 1
print(ans)


import sys
zz = 1
sys.setrecursionlimit(10 ** 5)
if zz:
	input = sys.stdin.readline
else:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('all.txt', 'w')
di = [[-1, 0], [1, 0], [0, 1], [0, -1]]

def fori(n):
	return [fi() for i in range(n)]

def inc(d, c, x=1):
	d[c] = d[c] + x if c in d else x

def ii():
	return input().rstrip()

def li():
	return [int(xx) for xx in input().split()]

def fli():
	return [float(x) for x in input().split()]

def comp(a, b):
	if a > b:
		return 2
	return 2 if a == b else 0

def gi():
	return [xx for xx in input().split()]

def gtc(tc, ans):
	print('Case #' + str(tc) + ':', ans)

def cil(n, m):
	return n // m + int(n % m > 0)

def fi():
	return int(input())

def pro(a):
	return reduce(lambda a, b: a * b, a)

def swap(a, i, j):
	(a[i], a[j]) = (a[j], a[i])

def si():
	return list(input().rstrip())

def mi():
	return map(int, input().split())

def gh():
	sys.stdout.flush()

def isvalid(i, j, n, m):
	return 0 <= i < n and 0 <= j < m

def bo(i):
	return ord(i) - ord('a')

def graph(n, m):
	for i in range(m):
		(x, y) = mi()
		a[x].append(y)
		a[y].append(x)
t = 1
uu = t
while t > 0:
	t -= 1
	(n, k) = mi()
	a = li()
	d = {}
	ans = 0
	for i in a:
		p = i
		j = 2
		r = []
		while j * j <= p:
			if p % j == 0:
				c = 0
				while p % j == 0:
					p //= j
					c += 1
				if c % k:
					r.append(j)
					r.append(c % k)
			j += 1
		if p >= 2:
			r.append(p)
			r.append(1)
		b = []
		for j in range(len(r)):
			if j % 2:
				b.append(k - r[j])
			else:
				b.append(r[j])
		ans += d.get(tuple(b), 0)
		inc(d, tuple(r))
	print(ans)


import os
import sys
from bisect import bisect_right
from collections import Counter, defaultdict
from heapq import *
from io import BytesIO, IOBase
from math import gcd, inf, sqrt, ceil

def lcm(a, b):
	return a * b // gcd(a, b)

def getFactorization(x):
	ret = list()
	while x != 1:
		ret.append(spf[x])
		x = x // spf[x]
	return ret

def printDivisors(n):
	i = 2
	z = [1, n]
	while i <= sqrt(n):
		if n % i == 0:
			if n / i == i:
				z.append(i)
			else:
				z.append(i)
				z.append(n // i)
		i = i + 1
	return z

def cheaker(a):
	j = 1
	p = False
	for i in a:
		if i != j:
			break
		j += 1
	q = len(a)
	for i in a[::-1]:
		if i != q:
			break
		q -= 1
	for i in range(j - 1, q):
		if a[i] == i + 1:
			return False
	return True

def create(n, x, f):
	pq = len(bin(n)[2:])
	if f == 0:
		tt = min
	else:
		tt = max
	dp = [[inf] * n for _ in range(pq)]
	dp[0] = x
	for i in range(1, pq):
		for j in range(n - (1 << i) + 1):
			dp[i][j] = tt(dp[i - 1][j], dp[i - 1][j + (1 << i - 1)])
	return dp

def enquiry(l, r, dp, f):
	if l > r:
		return inf if not f else -inf
	if f == 1:
		tt = max
	else:
		tt = min
	pq1 = len(bin(r - l + 1)[2:]) - 1
	return tt(dp[pq1][l], dp[pq1][r - (1 << pq1) + 1])

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	x = []
	for i in range(2, n + 1):
		if prime[i]:
			x.append(i)
	return x

def main():
	(n, k) = map(int, input().split())
	a = [int(x) for x in input().split()]
	z = {}
	an = 0
	for i in a:
		j = 2
		tt = []
		xx = []
		while j <= sqrt(i):
			c = 0
			while i % j == 0:
				i = i // j
				c += 1
			c = c % k
			if c:
				tt.append((j, c))
				xx.append((j, k - c))
			j += 1
		if i > 1:
			tt.append((i, 1))
			xx.append((i, k - 1))
		tt = tuple(tt)
		xx = tuple(xx)
		if tt not in z:
			z[tt] = 1
		else:
			z[tt] += 1
		if xx in z:
			an += z[xx]
		if tt == xx:
			an -= 1
	print(an)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()