搞一搞式子：(frac{operatorname{lcm}(x,y)}{gcd(x,y)}=p^2)。
把 (operatorname{lcm}) 弄掉：(xy=(p imesgcd(x,y))^2)。
也就是说 (xy) 必须是完全平方数才有关联，也就是说每个质因子出现次数的奇偶性必须相同，而这东西是有传递性的，我们可以把数根据每个质因子出现次数的奇偶性划分成若干个集合，存在某个质因子出现次数不同就归入不同集合，集合内两两均有关联。
显然经过第一秒同一集合内的数会变得相同，且质因子出现次数只存在奇变偶的情况。对于一个集合，如果其中的数变成了完全平方数，那么接下来也一直会是完全平方数。
如果其中的数仍然没有变成完全平方数，那么接下来也一直不会是完全平方数，这很好证。假设此时有某个集合并入了当前集合，说明那个集合的大小为偶数，而大小为偶数的集合里面均变成了完全平方数，与假设不符。
所以这些集合会一直独立且大小为奇数，每个质因子出现次数的奇偶性保持不变。
于是分 (w=0) 和 (w>0) 讨论即可，时间复杂度 (O(sumsqrt a+sum nlog n))。
code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 300005
#define Max(x,y)((x)>(y)?x:y)
#define For(i,x,y)for(i=x;i<=(y);i++)
int a[N],b[N];
ll read()
{
ll A;
bool K;
char C;
C=A=K=0;
while(C<'0'||C>'9')K|=C=='-',C=getchar();
while(C>'/'&&C<':')A=(A<<3)+(A<<1)+(C^48),C=getchar();
return(K?-A:A);
}
int main()
{
ll w;
int t,n,i,s,c,q,tot;
t=read();
while(t--)
{
n=read();
For(i,1,n)a[i]=read();
q=read();
For(i,1,n)
{
c=s=1;
while(a[i]>1)
{
if(++c>sqrt(a[i]))break;
while(!(a[i]%(c*c)))a[i]/=c*c;
if(!(a[i]%c))s*=c,a[i]/=c;
}
b[i]=s*a[i];
}
sort(b+1,b+n+1);
s=c=1;
tot=0;
For(i,2,n+1)
if(b[i]==b[i-1])s++;
else
{
c=Max(c,s);
if(b[i-1]==1||!(s&1))tot+=s;
s=1;
}
while(q--)w=read(),printf("%d
",(w?Max(tot,c):c));
}
return 0;
}
/*1
3
3 27 4
2
0
1*/