Strange Definition (Codeforces 1471D)
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 os
import sys
from io import BytesIO, IOBase
from collections import Counter, defaultdict
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        import os
        self.os = os
        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 = self.os.read(self._fd, max(self.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 = self.os.read(self._fd, max(self.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:
            self.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')

def ri():
    return int(input())

def rl():
    return list(map(int, input().split()))
from math import sqrt

def precompute_factorization_no_squares(N_MAX=10 ** 7 + 1):
    """"""
    squares = [i * i for i in range(1, int(sqrt(N_MAX)))]
    canonical_forms = [i for i in range(N_MAX + 1)]
    for i in range(1, N_MAX + 1):
        if canonical_forms[i] == i:
            for sq in squares:
                if i * sq > N_MAX:
                    break
                canonical_forms[i * sq] = i
    return canonical_forms
''
t = ri()
''
canonical_forms = list(range(10 ** 6 + 1))
for i in range(2, 1001):
    square = i * i
    for j in range(square, 10 ** 6 + 1, square):
        canonical_forms[j] = j // square
for testcase in range(t):
    n = ri()
    aa = rl()
    q = ri()
    ans0 = 0
    ans1 = 0
    C = Counter([canonical_forms[a] for a in aa])
    for val in C.keys():
        if val == 1 or C[val] & 1 == 0:
            ans1 += C[val]
        ans0 = max(ans0, C[val])
        C[val] = 0
    ans1 = max(ans1, ans0)
    for i in range(q):
        w = ri()
        if w == 0:
            print(ans0)
        else:
            print(ans1)

Solution (Python):
import sys, os
import math
if os.path.exists('in.txt'):
    sys.stdin = open('in.txt', 'r')
from io import BytesIO, IOBase

def main():
    pass
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')

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

def out(var):
    sys.stdout.write(str(var) + '\n')
if __name__ == '__main__':
    n = 10 ** 6
    sieve = [i for i in range(n + 1)]
    for i in range(2, n + 1):
        if sieve[i] == i:
            for j in range(i * i, n + 1, i):
                if sieve[j] == j:
                    sieve[j] = i
    from collections import defaultdict
    for _ in range(int(input())):
        n = int(input())
        arr = list(map(int, input().split()))
        dic = defaultdict(lambda : 0)
        for i in range(n):
            k = 1
            t = arr[i]
            while t > 1:
                if k % sieve[t] == 0:
                    k = k // sieve[t]
                else:
                    k *= sieve[t]
                t = t // sieve[t]
            dic[k] += 1
        out1 = 0
        for i in dic:
            out1 = max(out1, dic[i])
        out2 = dic[1]
        for i in dic:
            if i == 1:
                continue
            elif dic[i] % 2 == 0:
                out2 += dic[i]
        out2 = max(out2, out1)
        q = int(input())
        for i in range(q):
            w = int(input())
            if w == 0:
                print(out1)
            else:
                print(out2)

Solution (Python):
import os
import sys
from io import BytesIO, IOBase
from collections import Counter, defaultdict
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        import os
        self.os = os
        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 = self.os.read(self._fd, max(self.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 = self.os.read(self._fd, max(self.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:
            self.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')

def ri():
    return int(input())

def rl():
    return list(map(int, input().split()))
from math import sqrt

def precompute_factorization_no_squares(N_MAX=10 ** 7 + 1):
    no_square = list(range(N_MAX))
    for i in range(2, N_MAX):
        square = i * i
        for j in range(square, N_MAX, square):
            no_square[j] = j // square
    return no_square
''
t = ri()
canonical_forms = precompute_factorization_no_squares(10 ** 6 + 100)
for testcase in range(t):
    n = ri()
    aa = rl()
    q = ri()
    ans0 = 0
    ans1 = 0
    C = Counter([canonical_forms[a] for a in aa])
    for val in C.keys():
        if val == 1 or C[val] & 1 == 0:
            ans1 += C[val]
        ans0 = max(ans0, C[val])
        C[val] = 0
    ans1 = max(ans1, ans0)
    for i in range(q):
        w = ri()
        if w == 0:
            print(ans0)
        else:
            print(ans1)