https://codeforces.com/contest/1470/problem/B
I couldn't write an easy-to-understand sentence, so it's my thought dump memo. I want to be able to use this kind of commentary well.
--When considering two integers a and b, when $ \ frac {lcm (a, b)} {gcd (a, b)} $ is a square number, we call it adj. --There is an array a consisting of n ($ 1 \ leq n \ leq 3 \ cdot 10 ^ 5 $) elements, and the element a_i is $ 1 \ leq ai \ leq 10 ^ 6 $. --The array when t = 0 is given. --This array will be replaced with the following number for each element at the next time. Replace all elements of a (including $ a_i $) with or without multiplying all elements of $ a_i $ and adj --Answer the maximum number of adjs for that time (0 or greater) for multiple queries given.
In this problem, it is important that a number is a number that is not divisible by a square number.
After factoring the number into prime factors, if the number of each prime factor is 2 or more, it can be further divided by a square number. For example, if you consider $ 2 ^ 4 \ cdot 3 ^ 3 \ cdot 5 ^ 7 $, two $ 2 ^ 2 $, two $ 3 ^ 2 $, and two $ 5 ^ 2 $ are split, and if you divide them all (state b) (If you do), it will be $ 3 ^ 1 \ cdot 5 ^ 1 $. If each multiplier is even, the prime factor disappears because it can be divided until it reaches zero. If it is an odd number, 1 remains at the end.
In other words, the number in this state needs to include each prime factor only once when factoring into prime factors. Generally, this is called "square-free integer", and the fact that it is not divisible by a square number is called "square-free". Hereafter, such numbers are called SF numbers .
First, consider the expression of the condition that is adj. If $ f (a, b) = \ frac {lcm (a, b)} {gcd (a, b)} $, then $ f (a, b) = k ^ 2 $ (k is an arbitrary integer) There exists k. That is, k is a condition that adj is a square number.
Now, from the definition of lcm, gcd, we recall $ lcm (a, b) \ cdot gcd (a, b) = a \ cdot b
It will be. Think about this meaning. $ gcd (a, b) ^ 2 $ is a number that contains twice the common factor of a and b. Since the numerator is $ a \ cdot b $, it means that two common factors are included in each, so it is an operation to erase all of them.
For example, now the numbers $ a, b with the common factor $ x $ and $ p, q $ (that is, all common prime factors are contained in x) consisting of non-common prime factors except 1. Consider $. $ p and q $ do not have to be relatively prime factors. Since it can be expressed as $ a = xp $, $ b = xq $, considering $ f (a, b)
Now, do the following:
For each number of $ a_i $, if that number is divisible by a square number, make it an SF number. Let each element be the SF number b_i array b corresponding to each $ a_i $. Since all $ b_i $ are SF numbers, the prime factors are numbers that include only one at the maximum . This process is the same as factoring $ a_i $ into prime factors and replacing each prime factor number with the remainder divided by two.
For the element $ b_i = b_j $ with the same number of SFs, the original $ a_i and a_j $ are adj. First, consider the underlying $ a_i $ and $ a_j $. These contained only even prime factors. If this factor is prime (not included in one), it remains as a square number. Even if there are non-prime factors, they are square numbers because they contain even numbers of prime factors, so they all disappear or even numbers remain. Also, these two numbers include $ b_i $ and $ b_j $ themselves, but since they are common factors, they disappear by $ f (b_i, b_j) $ and become 1.
Conversely, elements with different numbers of SFs do not become adj. This is because the product of the non-common factors $ b_i $ and $ b_j $ is not a square number.
The SF number $ b_i $ is calculated from each $ a_i $. The number is counted for each SF number, and the largest number of elements is the answer.
Now, when transitioning from t = 0 to t = 1, an element with an adj number takes the product of an adj element (including myself).
Pay attention to the count of each SF number. Since elements with the same SF number have one prime factor, each prime factor will be included when transitioning to t = 1. Therefore, if the SF number count is even, the SF number will be 1 at the moment of t = 1. If it is an even number, each prime factor will be an even number, so when considering the SF number, it will all disappear to 1. (For example, if there are 4 elements with SF number $ 15 = 3 \ cdot 5 $, it will be $ 3 ^ 4 \ cdot 5 ^ 4 $, and if you calculate the SF number, all will disappear and become 1.) If it is odd, each prime factor will be odd and the SF number will be the same as the original again. (For example, if there are 3 elements of SF number $ 15 = 3 \ cdot 5 $, it will be $ 3 ^ 3 \ cdot 5 ^ 3 $, and since the SF number divides the square number, it will be $ 15 = 3 \ cdot 5 $ again. In other words, the number of elements with an odd number of SF counts does not change.
So what about the transition from t = 1 to t = 2? All elements have a SF number of 1, or the count of the SF number elements is odd. Therefore, even if the product by adj is taken again after t = 1, the number of elements will be the same as t = 1 (even after t = 2).
This time, the element of $ a_i $ is small, so pre-calculate all the maximum square numbers that can be divided for all numbers from 1 to $ 10 ^ 6 $. Based on this table, $ a_i $ is determined to be divisible by a square number, divided, and stored in b_i as an SF number.
When t = 0, the maximum value of each SF number count is the answer to be answered. Look at all SF numbers and save the largest of them as resT0 for t = 0 queries.
Next, consider the answer to the query after t = 1. Let's look at all numbers with SF numbers 2 and above. If this SF number count is even, set the SF number to 1 (that is, add that SF number count to the SF number 1 entry). If it is odd, leave it as it is. After that, count each SF number (including 1) and save the maximum value as resT1 for queries after t = 1.
As mentioned above, the query after t = 2 has the same answer as t = 1, so the same value should be returned.
Pre-calculate whether it can be divided by a square number.
import sys
import collections
import math
input = sys.stdin.readline
mnum = 10 ** 6 + 1000
mnumsqr = math.ceil(math.sqrt(mnum)) + 10
# mCanDivSqrt[x] x can div max(sqrt num)
# ex. 80 can be dived 4(2^2) or 16(4^2)
# this table ret maxnum = 16
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: # make SF-number
if mCanDivSqrt[x] != -1:
x //= mCanDivSqrt[x]
else: break
numbTable[x] += 1
nextBnum1 = numbTable[1] # anytime, 1 is good
res0 = max(nextBnum1,1) # res0 is time=0 max adj
for k in numbTable.keys(): # check all SF num!
if k == 1: continue
res0 = max(res0, numbTable[k])
if numbTable[k] % 2 == 0: # even count is good
nextBnum1 += numbTable[k] # this bnum will be bnum=1
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()
https://codeforces.com/contest/1470/submission/103978461
Take $ [3, 4, 12] $ as an example. The answer for t = 0 is 2 because it is $ [3, 2 ^ 2, 2 ^ 2 \ cdot3] $ and 3 and 12 have an adj relationship. And a at the moment of t = 1 becomes $ [2 ^ 2 \ cdot3 ^ 2, 2 ^ 2, 2 ^ 2 \ cdot3 ^ 2] $. At this time, the first and third terms are the same number, adj, and 4 also has an adj relationship with the first and third terms, so the answer for t = 1 is 3. t = 2 becomes $ [2 ^ 6 \ cdot3 ^ 4, 2 ^ 6 \ cdot3 ^ 4, 2 ^ 6 \ cdot3 ^ 4,] $, and t = 3 thereafter.
Take $ [3, 3, 4, 12] $ as an example. The answer for t = 0 is 3 because it is $ [3, 3, 2 ^ 2, 2 ^ 2 \ cdot3] $ and 3 and 3 and 12 are adj relations. And a at the moment of t = 1 becomes $ [2 ^ 2 \ cdot3 ^ 3, 2 ^ 2 \ cdot3 ^ 3, 2 ^ 2, 2 ^ 2 \ cdot3 ^ 3] $. At this time, the first, second, and third terms are the same number and are adj. Earlier, 4 also joined the adj relationship here, but 4 remains $ 3 ^ 3 $ regardless of which element is combined, and it does not become adj.