Strange Definition (Codeforces 1470B)
Tags: Math, hashing

Let us call two integers $$$x$$$ and $$$y$$$ adjacent if $$$\frac{lcm(x, y)}{gcd(x, y)}$$$ is a perfect square. For example, $$$3$$$ and $$$12$$$ are adjacent, but $$$6$$$ and $$$9$$$ are not.Here $$$gcd(x, y)$$$ denotes the greatest common divisor (GCD) of integers $$$x$$$ and $$$y$$$, and $$$lcm(x, y)$$$ denotes the least common multiple (LCM) of integers $$$x$$$ and $$$y$$$.You are given an array $$$a$$$ of length $$$n$$$. Each second the following happens: each element $$$a_i$$$ of the array is replaced by the product of all elements of the array (including itself), that are adjacent to the current value. Let $$$d_i$$$ be the number of adjacent elements to $$$a_i$$$ (including $$$a_i$$$ itself). The beauty of the array is defined as $$$\max_{1 \le i \le n} d_i$$$. You are given $$$q$$$ queries: each query is described by an integer $$$w$$$, and you have to output the beauty of the array after $$$w$$$ seconds.

Input: The first input line contains a single integer $$$t$$$ ($$$1 \le t \le 10^5)$$$ — the number of test cases.The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — the length of the array.The following line contains $$$n$$$ integers $$$a_1, \ldots, a_n$$$ ($$$1 \le a_i \le 10^6$$$) — array elements. The next line contain a single integer $$$q$$$ ($$$1 \le q \le 3 \cdot 10^5$$$) — the number of queries.The following $$$q$$$ lines contain a single integer $$$w$$$ each ($$$0 \le w \le 10^{18}$$$) — the queries themselves.It is guaranteed that the sum of values $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$, and the sum of values $$$q$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$

Output: For each query output a single integer — the beauty of the array at the corresponding moment.

Note: In the first test case, the initial array contains elements $$$[6, 8, 4, 2]$$$. Element $$$a_4=2$$$ in this array is adjacent to $$$a_4=2$$$ (since $$$\frac{lcm(2, 2)}{gcd(2, 2)}=\frac{2}{2}=1=1^2$$$) and $$$a_2=8$$$ (since $$$\frac{lcm(8,2)}{gcd(8, 2)}=\frac{8}{2}=4=2^2$$$). Hence, $$$d_4=2$$$, and this is the maximal possible value $$$d_i$$$ in this array.In the second test case, the initial array contains elements $$$[12, 3, 20, 5, 80, 1]$$$. The elements adjacent to $$$12$$$ are $$$\{12, 3\}$$$, the elements adjacent to $$$3$$$ are $$$\{12, 3\}$$$, the elements adjacent to $$$20$$$ are $$$\{20, 5, 80\}$$$, the elements adjacent to $$$5$$$ are $$$\{20, 5, 80\}$$$, the elements adjacent to $$$80$$$ are $$$\{20, 5, 80\}$$$, the elements adjacent to $$$1$$$ are $$$\{1\}$$$. After one second, the array is transformed into $$$[36, 36, 8000, 8000, 8000, 1]$$$.

Sample Inputs:
2
4
6 8 4 2
1
0
6
12 3 20 5 80 1
1
1

Sample Outputs:
2
3

Solution (Python):
import sys
import collections
import math
input = sys.stdin.readline
mnum = 10 ** 6 + 1000
mnumsqr = math.ceil(math.sqrt(mnum)) + 10
mCanDivSqrt = [-1] * (mnum + 10)
for i in range(2, mnumsqr):
    if i ** 2 < mnum + 1:
        cur = i ** 2
        x = cur
        while x <= mnum:
            mCanDivSqrt[x] = i ** 2
            x += cur

def do():
    n = int(input())
    dat = list(map(int, input().split()))
    numbTable = collections.defaultdict(int)
    for x in dat:
        while True:
            if mCanDivSqrt[x] != -1:
                x //= mCanDivSqrt[x]
            else:
                break
        numbTable[x] += 1
    nextBnum1 = numbTable[1]
    res0 = max(nextBnum1, 1)
    for k in numbTable.keys():
        if k == 1:
            continue
        res0 = max(res0, numbTable[k])
        if numbTable[k] % 2 == 0:
            nextBnum1 += numbTable[k]
    nextBnum1 = max(nextBnum1, res0)
    q = int(input())
    for _ in range(q):
        qnum = int(input())
        if qnum == 0:
            print(res0)
        else:
            print(nextBnum1)
q = int(input())
for _ in range(q):
    do()

Solution (Python):
from sys import stdin
from sys import stdout
squarefree = [int(i) for i in range(1000001)]
for i in range(2, 1001):
    ii = i * i
    j = 1
    while j * ii < 1000001:
        squarefree[j * ii] = j
        j += 1
t = int(stdin.readline())
while t > 0:
    mm = {}
    n = int(stdin.readline())
    a = list(map(int, stdin.readline().split()))
    max_d = 1
    for i in range(n):
        sfa_i = squarefree[a[i]]
        d_i = mm.get(sfa_i)
        if d_i == None:
            d_i = 1
        else:
            d_i += 1
        mm[sfa_i] = d_i
        max_d = max(max_d, d_i)
    amount_1 = 0
    for (key, value) in mm.items():
        if key == 1:
            amount_1 += value
        elif value % 2 == 0:
            amount_1 += value
    q = int(stdin.readline())
    for i in range(q):
        w = int(stdin.readline())
        if w == 0:
            stdout.write(str(max_d) + '\n')
        else:
            stdout.write(str(max(max_d, amount_1)) + '\n')
    t -= 1

Solution (Python):
from sys import stdin
dct = {i: i for i in range(1000001)}
for i in range(2, 1001):
    for j in range(1, 10 ** 6 // i ** 2 + 1):
        dct[i ** 2 * j] = j
t = int(stdin.readline())
for _ in range(t):
    n = int(stdin.readline())
    elements = map(int, stdin.readline().split())
    q = int(stdin.readline())
    dct2 = {}
    for i in elements:
        if dct[i] not in dct2:
            dct2[dct[i]] = 1
        else:
            dct2[dct[i]] += 1
    chan = 0
    maxx = 0
    for (so, gia) in dct2.items():
        if so == 1:
            maxx = max(gia, maxx)
            chan += gia
        else:
            maxx = max(gia, maxx)
            if gia % 2 == 0:
                chan += gia
    maxx2 = max(chan, maxx)
    for times in range(q):
        quer = stdin.readline()
        if quer == '0\n':
            print(maxx)
        else:
            print(maxx2)