分かりやすい文章が書けなかったので、自分の思考ダンプメモです。
こういう解説を上手くかけるようになりたいです。
題意
- 2つの整数a,bを考えたとき、$ \frac{lcm(a,b)}{gcd(a,b)} $ が平方数であるとき、$adj$であると呼ぶ
- n($1 \leq n \leq 3 \cdot 10^5$)個の要素からなる配列aがあり、要素a_iは$ 1 \leq a_i \leq 10^6$である。
- t=0の時の配列が与えられる。
- この配列は次の時間には各要素に対して次の数に置き換える。aのすべて($a_i$を含む)の要素に対して、$a_i$とadjであるすべての要素をかけたかずに置き換える
- 与えられる複数のクエリにたいして、その時間(0以上)の最大のadjの数を答えよ
前提知識: ある数に対する平方数の除算可能性 と SF数
この問題では、ある数が平方数でそれ以上割り切れない数かが大切になります。
その数を素因数分解をした後、各素因数の数が2以上であればさらに平方数で除算することが可能です。例えば、$2^4 \cdot 3^3 \cdot 5^7$を考えると、$2^2$が2つと$3^2$と$5^2$が２つで割れ、すべてを割ると(bの状態にすると)$3^1 \cdot 5^1$になります。各乗数が偶数であれば、0になるまで除算できるため、その素因数は消えます。奇数であれば最後に1残ります。
つまり、この状態の数は、素因数分解をしたときに各素因数が１度しか含まれないことが必要です。一般にこれを「無平方数(square-free integer)」と呼び平方数で割り切れない、ということを「無平方(square-free)」と呼びます。以下、このような数をSF数と呼びます
adjである条件の簡易化
まず、adjである条件の式を考えます。$f(a,b) = \frac{lcm(a,b)}{gcd(a,b)} $とすると、$f(a,b) = k^2 $ (kは任意の整数) となるkが存在する。つまり、kは平方数であることがadjである条件です。
ここで、lcm, gcdの定義から、$lcm(a,b) \cdot gcd(a,b) = a \cdot b$を思いだします。$$lcm(a,b) = \frac{a \cdot b}{gcd(a,b)} \Rightarrow f(a,b) = \frac{lcm(a,b)}{gcd(a,b)} = \frac{ab}{gcd(a,b)^2} $$
となります。この意味を考えます。$gcd(a,b)^2$はa,bの共通因数が2倍含まれている数です。分子は$a \cdot b$なので、共通因数がそれぞれ2つずつ含まれていることになりますので、それらをすべて消す操作となります。
例えば、今、共通の因数$x$を持ち、1を除く共通ではない素因数からなる$p,q$(つまり、共通な素因数はすべてxに含まれている)を持った数$a,b$を考えます。$p,q$は互いに素な因数でなくてよいです。$a=xp$, $b=xq$と表せるので、$f(a,b)$を考えると、
$$ f(a,b) = \frac{lcm(a,b)}{gcd(a,b)} = \frac{x \cdot pq}{x} = pq$$
となり、共通因数$x$が消えたことが分かります。すなわち、$pq$が平方数であるとき、$adj$です。$pq$が平方数である条件を考えると、以下のいずれかを満たすことが必要です。
- 条件1: いずれも1である
- 条件2: pとqに含まれるすべての各素因数について、その合わせた合計が偶数である。
条件1については$pq=1=1^2$で自明です。条件2は各素因数が偶数個であれば、必ず$k^2$の形にできます。
問題の解き方
さて、ここで、次のように処理を行います。
各$a_i$の数について、その数が平方数で除算可能なら、SF数にします。それぞれの$a_i$に対応するSF数$b_i$を配列$b$の各要素をとしましょう。すべての$b_i$は、SF数ですから素因数は最大で1つしか含まれない数になります。この処理は、$a_i$を素因数分解し、各素因数の数について2で割ったあまりの数に置き換える動作と同じです。
SF数が同じ要素$b_i = b_j$について、元となった$a_i, a_j$はadjです。
まず、元となる$a_i$と$a_j$を考えます。これらには偶数個の素因数だけが含まれていました。この因数が素(一方には含まれていない)であれば、その因数は平方数として残りますｌ。もし、素でない因数があったとしても、互いにその素因数が偶数個含まれているので、すべて消えるか、偶数個の素因数が残るため平方数です。また、この２つの数には$b_i$と$b_j$自身が含まれますが、これらは、共通の因数であるため、$f(b_i, b_j)$により消えて1になります。
逆に、SF数が異なる要素はadjにはなりません。なぜなら、共通ではない因数$b_i$, $b_j$の積は平方数にならないからです。
※$b_i=3$, $b_j=15$などを考えると、3は消えますが5は残ります
t=0の時
各$a_i$からSF数$b_i$を求めてます。SF数毎に数をカウントし、最も大きい要素数が答えです。
t=1の時
さて、t=0からt=1に遷移するとき、adjな数のある要素は(自分を含めた)adjな要素との積をとります。
各SF数のカウントに注目します。同じSF数の要素はある素因数を1つずつ持つため、t=1に遷移する際、各素因数を含むことになります。
そのため、SF数のカウントが偶数の場合、t=1の瞬間にはそのSF数は1になります。偶数ならば各素因数は偶数になるため、そのSF数を考える際にすべて消え切ります1になります。(例えば、SF数$15=3 \cdot 5$の要素が4つあった場合、$3^4 \cdot 5^4$となり、SF数を求めるとすべて消えて1になります)
奇数の場合、各素因数は奇数個となり、SF数は再び元と同じになります。(例えば、SF数$15=3 \cdot 5$の要素が3つあった場合、$3^3 \cdot 5^3$となり、SF数は平方数を除するので再び$15=3 \cdot 5$に戻ります。)つまり、SF数のカウントが奇数個の要素数は変わりません。
t=2以降の時
それでは、t=1からt=2の遷移ではどうでしょうか？すべての要素はSF数が１であるか、そのSF数の要素のカウントが奇数個です。このため、t=1になった後、再度adjによる積を取っても(t=2以降も)t=1と同じ要素数になります。
前処理とクエリへの対応を考える。
今回、$a_i$の要素は小さいので、1から$10^6$のすべての数について除算できる最大の平方数をすべて事前計算しておきます。このテーブルを元にして$a_i$は平方数で除算可能かを判定して割り、SF数としてb_iに格納します。
t=0の時は、各SF数のカウントの最大値が答えるべき答えです。すべてのSF数を見て、そのうちの最大の値をresT0としてt=0クエリ向けに保存します。
次にt=1以降のクエリの答えを考えます。SF数が2以上のすべての数を見ていきます。このSF数のカウントが偶数なら、SF数を1にします(つまりそのSF数のカウントをSF数1のエントリに追加します)。奇数の場合はそのままにします。そのあと、(1を含めて)各SF数のカウントを行い、そのうちの最大の値をresT1としてt=1以降のクエリ向けに保存します。
t=2以降のクエリは前述の通り、答えはt=1と変化が無いため、同じ値を返せばよいです。
実装
平方数で除算できるかの事前計算を行います。
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()
いくつかの具体例
$[3, 4, 12]$を例にとります。$[3, 2^2, 2^2\cdot3]$であり、3と12がadjの関係のため、t=0の答えは2です。そして、t=1の瞬間のaは$[2^2\cdot3^2, 2^2, 2^2\cdot3^2]$となります。この時、第1項と第3項は同じ数であり、adjで、さらに4も第1項, 第3項とadj関係となるため、t=1の答えは3です。t=2は$[2^6\cdot3^4, 2^6\cdot3^4, 2^6\cdot3^4,]$となり、以降のtでは3となります。
$[3, 3, 4, 12]$を例にとります。$[3, 3, 2^2, 2^2\cdot3]$であり、3と3と12がadjの関係のため、t=0の答えは3です。そして、t=1の瞬間のaは$[2^2\cdot3^3, 2^2\cdot3^3, 2^2, 2^2\cdot3^3]$となります。この時、第1,2,3項は同じ数でありadjです。さきほどはここで、4もadjの関係に加わりましたが、4はいずれの要素と組んでも$3^3$が残り、adjにはなりません。