《 离 散 数 学 学 疯 以 后 》
【题目大意】
定义关系 \(R\) ，若 \(\text{lcm}(x,y)\over \gcd(x,y)\) 为完全平方数，则 \(x\ R\ y\) 。
现给定长度为 \(n\) 的序列 \(a\) 。每次操作会将元素 \(a_i\) 替换为所有与之具有关系 \(R\) 的元素的乘积（包括它自己），即 \(a_i\leftarrow \displaystyle \prod_{a_i\ R\ a_j}a_j\) 。
另外定义 \(d_i\) 表示与 \(a_i\) 具有关系 \(R\) 的元素的个数，定义序列的特征为 \(d_i\) 的最大值。
现有 \(q\) 个询问，每次询问给定 \(w\) ，输出 \(w\) 次操作后的序列的特征值。
【分析】
\(\because \text{lcm}(x,y)={xy\over \gcd(x,y)}\)
\(\therefore {\text{lcm}(x,y)\over \gcd(x,y)}={xy\over \gcd(x,y)^2}\)
\(\because \gcd(x,y)^2\) 为完全平方数
\(\therefore {xy\over \gcd(x,y)^2}\) 为完全平方数 \(\Leftrightarrow\) \(xy\) 为完全平方数
即若 \(xy\) 为完全平方数，则 \(x\ R\ y\)
不难发现，关系 \(R\) 具有以下三个特性：
- 自反性：\(x^2\) 为完全平方数 \(\Rightarrow\) \(x\ R\ x\)
- 对称性：\(x\ R\ y\) \(\Rightarrow\) \(xy\) 为完全平方数 \(\Rightarrow\) \(y\ R\ x\)
- 传递性：\(x\ R\ y\wedge y\ R\ z\) \(\Rightarrow\) \(xy,yz\) 为完全平方数 \(\Rightarrow\) \(xzy^2=xy\cdot yz\) 为完全平方数
\(\because y^2\) 为完全平方数 \(\therefore xz\) 为完全平方数 \(\Rightarrow\) \(x\ R\ z\)
因此关系 \(R\) 为等价关系，能将序列 \(a\) 分为若干等价类
因此，序列的特征等价于所有等价类大小的最大值；每次操作相当于将等价类内部的元素，替换成等价类所有元素的乘积
对于一个等价类 \(P\) ，由唯一质数分解定理，一定存在一个各质因子次数都不大于 \(1\) 的数 \(r\) ，使得 \(\forall x\in P\leftrightarrow (\exist n\in N\wedge x=r\cdot n^2)\)
证明：设 \(\exist x,y\in P,n\in N\wedge x=r\cdot n^2\)
\(\because xy=ry\cdot n^2\) 为完全平方数，\(n^2\) 为完全平方数
\(\therefore ry\) 为完全平方数
\(\because r\) 各质因子次数不大于 \(1\)
\(\therefore y=r\cdot m^2,m\in N\)
因此各等价类可由各自的 \(r\) 作为其特征
对于一个等价类 \(P\) ，若 \(|P|\) 为偶数，则一次变化后，特征 \(r\) 变为 \(1\) ；若 \(|P|\) 为奇数，则一次变化后，特征 \(r\) 不变
因此，第一次操作前，序列的特征为最大的等价类
第一次操作后，原长度为偶数的等价类与原特征为 \(1\) 的等价类合并，原长度为奇数的等价类不变；序列的特征或为原长度为偶数的等价类大小，与原特征为 \(1\) 的等价类大小之和，或为长度为奇数的等价类大小
第二次操作及之后，等价类不再发生变化，答案不变
故仅需预处理第一次变化前的各等价类大小，即可预处理出第一次操作前后的答案，从而得出所有答案
【代码】
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=3e5+10;
int N;
map<int,int> m;
inline void work(){
m.clear();
cin>>N;
for(int i=1;i<=N;i++){
int A;
cin>>A;
for(int j=2;j*j<=A;j++)//找出对应的 r
while(A%(j*j)==0) A/=j*j;
++m[A];//记录至等价类
}
int Ans0=0,Ansodd=0,Ans1=0;
for(auto e : m){
Ans0=max(Ans0,e.second);//等价类大小最大值，w=0时的答案
if(e.second&1) Ansodd=max(Ansodd,e.second);//等价类大小为奇数的最大值
else Ans1+=e.second;//第一次操作后，等价类大小为偶数的合并
}
if(m[1]&1) Ans1+=m[1];//特征为 1 的等价类还未合并
Ans1=max(Ans1,Ansodd);//w>0 时的答案
ll Q,W;
cin>>Q;
while(Q--&&cin>>W)
if(W) cout<<Ans1<<"\n";
else cout<<Ans0<<"\n";
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int T;
cin>>T;
while(T--) work();
cout.flush();
return 0;
}