G7006 [GESP202406 七级] 区间乘积 题解

知识点：前缀异或、质因数、状态压缩。

解题思路

用10位掩码记录2到29这10个素数的指数奇偶性，边读数边异或前缀状态；遇到与历史相同的状态，就增加其出现次数。

为什么正确

区间乘积为平方当且仅当每个质因子指数均为偶数，也就是两个前缀奇偶掩码相同。

易错点

素数表利用题目a_i范围，不可直接用于含更大质因子的扩展输入；空前缀状态0要先计一次。

复杂度

时间O(n log A)，空间O(2^10)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    int primes[]= {
        2,3,5,7,11,13,17,19,23,29
    }
    ;
    vector<long long>cnt(1024);
    cnt[0]=1;
    int mask=0;
    long long ans=0;
    while(n--) {
        int x;
        cin>>x;
        for(int j=0;j<10;j++)while(x%primes[j]==0) {
            x/=primes[j];
            mask^=1<<j;
        }
        ans+=cnt[mask]++;
    }
    cout<<ans;
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用16个自行生成的测试点。