Power Products (Codeforces 1247D)
Tags: Others, number theory

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.

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

Sample Inputs:
6 3
1 3 9 8 24 1

Sample Outputs:
5

Solution (Python):
def isPrime(n):
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True
from math import ceil
import math
from math import gcd
import bisect
from bisect import bisect_right
from itertools import combinations
from collections import Counter
ceil1 = lambda a, b: (a + b - 1) // b
cubic_root = lambda n: round(math.exp(math.log(n) / 3), 6)
range_sum = lambda l, r: (l + r) * (r - l + 1) // 2
primes = [2]
for i in range(3, 317, 2):
    for j in range(3, i, 2):
        if i % j == 0:
            break
    else:
        primes.append(i)

def solve():
    (n, k) = list(map(int, input().split()))
    ans = 0
    arr = list(map(int, input().split()))
    d = Counter()
    for x in arr:
        key = []
        req = []
        for p in primes:
            if x % p == 0:
                count = 0
                while x % p == 0:
                    count += 1
                    x //= p
                count %= k
                if count:
                    key.append((p, count))
                    req.append((p, k - count))
        if x > 1:
            key.append((x, 1))
            req.append((x, k - 1))
        ans += d[tuple(req)]
        d[tuple(key)] += 1
    print(ans)
solve()

Solution (Python):
from sys import stdin

def rl():
    return [int(w) for w in stdin.readline().split()]
from collections import Counter
(n, k) = rl()
a = rl()
N = 100000
f = [None] * (N + 1)
f[0] = f[1] = {}
sqk = [False] * (N + 1)
sqk[0] = sqk[1] = True
for p in range(2, N + 1):
    if f[p] is None:
        for x in range(1, N // p + 1):
            if f[x] is None:
                continue
            fxp = f[x].copy()
            if p in fxp:
                fxp[p] += 1
                if fxp[p] == k:
                    del fxp[p]
            else:
                fxp[p] = 1
            f[x * p] = fxp
cofs = [str({p: k - e for (p, e) in fi.items()}) for fi in f]
fs = [str(fi) for fi in f]
b = Counter([fs[ai] for ai in a])
c = Counter([cofs[ai] for ai in a])
fsq = {fs[ai] for ai in a if fs[ai] == cofs[ai]}
r = 0
for x in b:
    r += b[x] * (b[x] - 1) if x in fsq else b[x] * c[x]
print(r // 2)

Solution (Python):
import collections
import sys
input = sys.stdin.readline

def read_i():
    return list(map(int, input().split()))

def factorize_all(n):
    factorizations = [None] * (n + 1)
    factorizations[0] = {}
    factorizations[1] = {}
    for p in range(2, n + 1):
        if factorizations[p] is None:
            for k in range(1, n // p + 1):
                if factorizations[k] is None:
                    continue
                fs = factorizations[k].copy()
                if p in fs:
                    fs[p] += 1
                else:
                    fs[p] = 1
                factorizations[k * p] = fs
    return factorizations
(n, k) = read_i()
ls = read_i()
m = max(ls)
pfs = factorize_all(m)
ls = collections.Counter(ls)
counter = collections.Counter()
pairs = set()
for (x, c) in ls.items():
    pf = pfs[x]
    x = 1
    y = 1
    for (p, v) in pf.items():
        v %= k
        if v > 0:
            x *= p ** v
            y *= p ** (k - v)
    counter[x] += c
    pairs.add((x, y))
res = 0
for (x, y) in pairs:
    if x == y:
        res += counter[x] * (counter[x] - 1)
    else:
        res += counter[x] * counter[y]
print(res // 2)