题意：

定义数字 x 和 y 是“相邻”的当且仅当 lcm(x,y)/gcd(x,y) 是一个平方数。
给定一个长度为 n 的数组 a。
每过一秒，数组 a 会发生变化：ai 会变成数组 a 中与其“相邻”的所有数字的乘积。
定义 di 为数组 a 中与 ai “相邻” 的数字个数。
定义数组 a 的美丽值为 max1≤i≤ndi
给出 q 个询问，每次询问给出当前时间 w，问当前数组 a 的美丽值。

题解：

参考题解
不会做。。emmm。。。看完题解恍然大悟
题目中w的范围0≤w≤10^18^,那说明不可能真的一轮一轮进行，因为w太大了，可能会存在a数组发生优先次变化后，答案就固定了
题目所定义的“相邻”经过简化后可得
在这里插入图片描述
分母为（gcd(x,y)）^2^,分子为x * y，为了让整体变成平方数，那说明x * y就是平方数，根据唯一分解定理，任何一个数都可以分解成质因数相乘的形式，x * y 为平方数，说明x和y对应的质因子的幂次奇偶性是相同的。（就比如x可以分解出一个3，那么y肯定也要分解出一个3，这样才能凑出平方）
现在我们对x和y进行处理，将x和y中偶数次幂的质因子删除掉，只留下奇数次幂的质因子。（因为偶数次的本身就是平方数了，对题目没有影响，有影响的是奇数）
处理后的到X和Y，如果X = = Y，x * y 就是平方数，否则就不是
接下来我们来处理美丽值这个问题
在a数组中没出现次数最多的数字的出现次数就是数组a的美丽值
a数组每轮都是会发生改变的，我们前面说了只有X== Y时，X与Y才是相邻的，那么与a[i]相邻的有d[i]个数，a[i]就变成了a[i]^d[i]^
我们接着对处理后的A数组进行质因数删除，只保留奇数次幂的质因子
如果d[i]是偶数，那么a[i]就变成了1，否则还是a[i]
我们发现变成1的数，之后再也不会发生改变了，相当于固定了，而没变成1的数永远都不是1,（是它本身）
因为没变成1的数说明是奇数个，那么与A[i]相邻的数也是奇数个，相当于A[i]变化后是A[i]^d[i]^,d[i]为奇数，而A[i]^d[i]^经过质因数删除操作后又得到A[i],所以永远不可能是1
说明：变化1次和变化多次的答案是一样的
也就是当w>=1时，我们只需要比较不变化的1的个数和变化1次后1的个数，输出最大值就行
变化后1的数量 = 还未变化时出现次数为偶数的非1的数字 + 原本1的数量
题目非常巧妙，好好揣摩

代码：

情况数组时最好不要用memset了，特别是大数据。。。。
不然
在这里插入图片描述

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);
   return s*w;
}
const int maxn=1e6+9;
int prime[maxn],tot,tag[maxn];
void Prime(int N){
    tag[0]=tag[1]=1;
    for(int i=2;i<=N;i++)
    {
        if(tag[i]==0)prime[tot++]=i;
        for(int j=0;j<tot&&i*prime[j]<N;j++)
        {
            tag[i*prime[j]]=1;
            if(i%prime[j]==0)break;
        }
    }
}
int a[maxn],sum[maxn];
vector<int>vec;
int main()
{
    int T;
    T=read();
    Prime(1000000);
    while(T--)
    {
        vec.clear();
        int n;
        n=read();
        int maxx=0;//maxx表示出现此处最多的数字的出现次数 
        int one=0;//记录没变化时1的数量 

        //memset(a,0,sizeof(a));
        for(int i=1;i<=n;i++)a[i]=read();
        for(int i=1;i<=n;i++)
        {
            int tmp=1;//tmp为奇数个质因子的乘积 
            int j=0;
            while(a[i]>=prime[j])
            {
                int num=0;
                while(a[i]%prime[j]==0)
                {
                    num++;
                    a[i]/=prime[j];
                }
                if(num%2==1)tmp=tmp*prime[j];//如果该质因数分解除奇数
                j++;
                if (!tag[a[i]]) {
                    tmp *= a[i];
                    break;
                }
            }
            //sum用来处理后，有多少数是相同的 
            vec.push_back(tmp); 
            maxx=max(maxx,++sum[tmp]);
        }

        int even=0;
        for(int x:vec)
        {
            if(x!=1)
            {
                if(sum[x]%2==0)///未变化时出现次数为偶数且非 1 的数字数量
                    even++; 
            }
            else
            {
                one++;
            }
        }
        for (int v : vec) {
            sum[v] = 0;
        }
        int q;
        q=read();
        while(q--)
        {
            ll w;
            scanf("%lld",&w);
            if(w==0)printf("%d\n",maxx);
            else printf("%d\n",max(maxx,one+even));
        }
    }
    return 0;
}