赛后想了想第三题，写了个代码。自己测的小范围数据是没问题的，大家可以参考

#include <iostream>
#include <map>
using namespace std;

using ll = long long;
const int N = 1e6 + 5;
int prime[N], a[N];
int vis[N];
int n, m;

void initPrime(int n)
{
    int cnt = 0;
    fill(vis, vis + N, 0);
    for(int i = 2; i <= n; i++)
    {
        if(vis[i] == 0) {vis[i] = i; prime[++cnt] = i;}
        for(int j = 1; j <= cnt; j++)
        {
            if(1ll * prime[j] * i > n) break;
            vis[prime[j] * i] = prime[j]; //最小素因子
            if(i % prime[j] == 0) break;
        }
    }
}

struct HashRoll {
    static const long long BASE1 = 131, BASE2 = 233;
    static const long long MOD1 = 1000000007, MOD2 = 1000000009;
    static pair<ll, ll> get(const map<int, int>& data) {
        long long h1 = 0, h2 = 0;
        for (auto [k, v] : data) {
            if(v == 0) continue; 
            h1 = (h1 * BASE1 + k * 7) % MOD1;
            h2 = (h2 * BASE2 + k * 13) % MOD2;
        }
        return {h1, h2};
    }
};

void getPrimer(int x, map<int, int>& mp) {
    while(x > 1) {
        int p = vis[x];
        mp[p] ^= 1; // 只记录奇数次出现的素因子
        x /= p;
    }
}

// 题意 ： 返回最长子数组长度，满足子数组内每个数的素因子出现偶数次
// 时间复杂度 O(n log(max(a[i]))), 空间复杂度 O(n)， 在1e6范围内不会TLE
/*
思路： 前缀哈希 + 哈希滚动
对每个前缀积分解质因数，记录每个质因数出现的次数的奇偶性

用哈希滚动记录前缀积的质因数奇偶性状态
(朴素想法是直接用n个map数组保存不同前缀积的状态，然后每次去对比不同map的状态是否一致，但这样每次对比map是否一致复杂度过高，因此直接将map状态hash即可，这里用双hash是为了降低冲突概率)
如果a[0]到a[l]前缀状态和a[0]到a[r]的前缀状态相同，说明中间的子数组a[l+1]到a[r]的乘积的每个质因数出现偶数次，那么这个子数组乘积是一个完全平方数（每个质因数的指数都是偶数，显然）
用哈希表记录每个前缀状态第一次出现的位置，更新最长子数组长度ans
*/
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> n;
    initPrime(1e6);
    for(int i = 1; i <= n; i++) cin >> a[i];
    map<int, int> mp; // 记录的是前缀积质因分解后每个质因数出现次数的奇偶性
    map<pair<ll, ll>, int> mp2; // 记录的是某种前缀积状态第一次出现的下标
    mp2[{0, 0}] = 0; // 初始状态
    int ans = -1;
    for(int i = 1; i <= n; i++) {
        getPrimer(a[i], mp);
        auto hashPair = HashRoll::get(mp);
        if(mp2.count(hashPair)) { // 如果存在同状态，说明中间子数组乘积质因数出现次数均为偶数次，是完全平方，故更新答案
            ans = max(ans, i - mp2[hashPair]);
        }
        else mp2[hashPair] = i; // 不存在该状态。代表第一次出现该状态，记录下标
    }
    cout << ans << "\n";
    return 0;
}

#恒生电子#