醉了

这题在能力范围内。

思路、方向都想对了。但是最后统计答案时的细节没想好,醉了!!!
一直卡在最后统计答案上面。该说是没有手感吗?该说是生疏吗?
艹!!
本来能上不少分的!!
艹!!

来说思路吧!!
我数论不会,所以这题在我看到gcd、lcm的时候心里一凉。
并没有打算用数学的方法去解。
我是达标规律做的。
我打了1到300所有数,在1到300范围内的临近数们。
这一打表,我就找到规律了。
对于数num = a * b^2 令b最大
他等价于 a
所以,我们最初都可以进行数的简化
又然后,在进行合并的过程中。
对于一群同类数进行合并时,我们可以看到最终会变为a^k * c^2
c = b1b2b3......
如果k为偶数那么,就变为了1 * c^2
就永远变成了1的同类项
如果为奇数就变为了a*c^2
即不变。

所以,我们找到了规律。按照这个规律做就可以了。
我是利用筛法求解每一个数的本质的。
对每一个数进行暴力求解的话是会超时的!!!

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<cmath>
using namespace std;
typedef long long ll;
const int max_n = 3e5+100;
int b[max_n*4];
int a[max_n];
ll n,q;
int main(){
    ios::sync_with_stdio(0);
    for (int i=1;i<=1000;++i)
        for (int j=i*i;j<=1000000;j+=i*i)
            b[j]=j/(i*i);
    int t;cin>>t;
    while(t--){
        cin>>n;
        for (int i=1;i<=n;++i)cin>>a[i],a[i]=b[a[i]];
        sort(a+1,a+1+n);
        vector<int> v;v.push_back(1);
        for (int i=2;i<=n;++i){
            if (a[i]==a[i-1]){
                v.back()++;
            }else v.push_back(1);
        }
        int ans1=0,ans2=0;
        for (int ans : v)ans1=max(ans1,ans);
        for (int ans : v)if (ans%2==0)ans2+=ans;
        if (a[1]==1&&v[0]%2!=0)ans2+=v[0];
        for (int ans : v)if (ans&1)ans2=max(ans2,ans);
        cin>>q;
        while (q--){
            ll w;cin>>w;
            if (w==0)cout<<ans1<<endl;
            else cout<<ans2<<endl;
        }
    }
}