这是一个用于生成 P10724 [GESP202406 七级] 区间乘积 题目测试数据的完整 C++ 代码。

这个生成器会生成 10 组测试数据（1.in/1.out 到 10.in/10.out），涵盖了题目中定义的三个子任务以及各种边界情况。

数据生成器代码 (generator.cpp)

你可以将以下代码保存为 generator.cpp，编译并运行。它将在当前目录下生成所有的输入输出文件。

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <random>
#include <ctime>
#include <map>

using namespace std;

// ==========================================
// 1. 标准解法函数 (用于生成 .out 文件)
// ==========================================

// 30以内的质数，共10个
const int primes[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};

// 计算数值 val 对应的状态掩码
int get_mask(int val) {
    int mask = 0;
    for (int i = 0; i < 10; ++i) {
        int p = primes[i];
        if (val < p) break; 
        int count = 0;
        while (val % p == 0) {
            count++;
            val /= p;
        }
        if (count % 2 == 1) {
            mask |= (1 << i);
        }
    }
    return mask;
}

// 核心求解逻辑
long long solve(int n, const vector<int>& a) {
    // mask 最大为 2^10 - 1 = 1023，开 1024 大小足够
    vector<int> cnt(1024, 0);
    
    // S_0 = 0，初始状态
    cnt[0] = 1;
    
    int current_mask = 0;
    long long ans = 0;
    
    for (int i = 0; i < n; ++i) {
        int mask = get_mask(a[i]);
        
        // 更新当前的前缀异或和
        current_mask ^= mask;
        
        // 如果 current_mask 之前出现过 k 次，则有 k 个合法区间
        ans += cnt[current_mask];
        
        // 记录当前 mask 出现的次数
        cnt[current_mask]++;
    }
    
    return ans;
}

// ==========================================
// 2. 数据生成逻辑
// ==========================================

mt19937 rng(time(0));

// 生成 [l, r] 范围内的随机整数
int rand_int(int l, int r) {
    uniform_int_distribution<int> dist(l, r);
    return dist(rng);
}

void generate_case(int id) {
    string in_name = to_string(id) + ".in";
    string out_name = to_string(id) + ".out";
    
    ofstream fout_in(in_name);
    ofstream fout_out(out_name);
    
    int n;
    vector<int> a;
    
    // 根据测试点编号配置参数，覆盖所有子任务
    switch(id) {
        // --- 子任务 1: n <= 10^5, a_i <= 2 ---
        case 1: // 小规模随机
            n = 10;
            for(int i=0; i<n; ++i) a.push_back(rand_int(1, 2));
            break;
        case 2: // 大规模随机
            n = 100000;
            for(int i=0; i<n; ++i) a.push_back(rand_int(1, 2));
            break;
            
        // --- 子任务 2: n <= 100, a_i <= 30 ---
        case 3: // 小规模随机
            n = 10;
            for(int i=0; i<n; ++i) a.push_back(rand_int(1, 30));
            break;
        case 4: // 全是完全平方数 (1, 4, 9, 16, 25) -> 答案应为 n*(n+1)/2
            n = 50;
            {
                int squares[] = {1, 4, 9, 16, 25};
                for(int i=0; i<n; ++i) a.push_back(squares[rand_int(0, 4)]);
            }
            break;
        case 5: // 特定质因数 (只包含2和3的倍数)
            n = 100;
            for(int i=0; i<n; ++i) {
                int val = 1;
                if(rand_int(0, 1)) val *= 2;
                if(rand_int(0, 1)) val *= 3;
                // 偶尔乘个平方数
                if(rand_int(0, 1)) val *= 4;
                a.push_back(val);
            }
            break;
        case 6: // 边界 n=100
            n = 100;
            for(int i=0; i<n; ++i) a.push_back(rand_int(1, 30));
            break;
            
        // --- 子任务 3: n <= 10^5, a_i <= 30 ---
        case 7: // 中等规模随机
            n = 1000;
            for(int i=0; i<n; ++i) a.push_back(rand_int(1, 30));
            break;
        case 8: // 大规模，只有质数 (状态变化频繁)
            n = 50000;
            {
                vector<int> p_list;
                for(int p : primes) p_list.push_back(p);
                for(int i=0; i<n; ++i) a.push_back(p_list[rand_int(0, 9)]);
            }
            break;
        case 9: // 大规模随机
            n = 100000;
            for(int i=0; i<n; ++i) a.push_back(rand_int(1, 30));
            break;
        case 10: // 最大规模，混合模式 (包含大量重复模式)
            n = 100000;
            for(int i=0; i<n; ++i) {
                if(i % 10 < 5) a.push_back(rand_int(1, 5)); // 小数
                else a.push_back(rand_int(20, 30)); // 大数
            }
            break;
    }
    
    // 写入输入文件
    fout_in << n << endl;
    for(int i=0; i<n; ++i) {
        fout_in << a[i] << (i == n-1 ? "" : " ");
    }
    fout_in << endl;
    
    // 计算并写入输出文件
    long long ans = solve(n, a);
    fout_out << ans << endl;
    
    fout_in.close();
    fout_out.close();
    
    cout << "Generated Case " << id << ": n=" << n << " answer=" << ans << endl;
}

int main() {
    // 生成 1 到 10 号测试点
    for(int i=1; i<=10; ++i) {
        generate_case(i);
    }
    cout << "All test cases generated successfully!" << endl;
    return 0;
}

测试点说明

1. Case 1: $N=10, a_i \in \{1, 2\}$。符合子任务 1，用于基本逻辑验证。
2. Case 2: $N=100000, a_i \in \{1, 2\}$。符合子任务 1 的大数据，测试 $O(N)$ 性能。
3. Case 3: $N=10, a_i \in [1, 30]$。符合子任务 2，基础随机。
4. Case 4: $N=50$，所有 $a_i$ 均为完全平方数。此时任何区间的乘积都是完全平方数，答案应为 $N(N+1)/2$，用于测试算法正确性。
5. Case 5: $N=100$，构造只包含质因子 2 和 3 的数，测试对特定质因子组合的处理。
6. Case 6: $N=100$，符合子任务 2 的最大边界。
7. Case 7: $N=1000$，过渡数据。
8. Case 8: $N=50000$，只由质数组成，测试前缀异或和变化频繁的情况。
9. Case 9: $N=100000$，符合子任务 3 的完全随机大数据。
10. Case 10: $N=100000$，混合分布的大数据，模拟真实场景。

使用方法

1. 将代码保存为 generator.cpp。
2. 使用 C++ 编译器编译：g++ generator.cpp -o generator -O2。
3. 运行生成的可执行文件：./generator（Windows 下是 generator.exe）。
4. 程序运行结束后，当前目录下会出现 1.in 到 10.in 以及 1.out 到 10.out 共 20 个文件。

这是一个基于数论和前缀和思想的题目。

题目分析

1. 完全平方数的性质：一个正整数是完全平方数，当且仅当其质因数分解中，每一个质因数的指数都是偶数。
2. 区间乘积：区间 $[l, r]$ 的乘积 $P = a_l \times a_{l+1} \times \dots \times a_r$。 对于任意质数 $p$，其在 $P$ 中的指数 $v_p(P)$ 等于区间内所有数中 $p$ 的指数之和：$v_p(P) = \sum_{k=l}^r v_p(a_k)$。 要使 $P$ 为完全平方数，需满足对于所有质数 $p$，$\sum_{k=l}^r v_p(a_k) \equiv 0 \pmod 2$。
3. 状态压缩与异或： 由于 $a_i \le 30$，涉及的质数只有 2, 3, 5, 7, 11, 13, 17, 19, 23, 29，共 10 个。 我们可以用一个长度为 10 的二进制数（bitmask）来表示一个数的状态。第 $j$ 位为 1 表示第 $j$ 个质数的指数是奇数，为 0 表示是偶数。 根据异或运算性质（相加模 2 等价于异或），区间乘积的状态等于区间内所有数的 mask 的异或和。 即：$Mask(P) = Mask(a_l) \oplus Mask(a_{l+1}) \oplus \dots \oplus Mask(a_r)$。 我们要找的是 $Mask(P) = 0$ 的区间。
4. 前缀异或和： 定义前缀异或和 $S_i = Mask(a_1) \oplus \dots \oplus Mask(a_i)$，且 $S_0 = 0$。 则 $Mask(a_l \times \dots \times a_r) = S_r \oplus S_{l-1}$。 条件 $Mask(P) = 0$ 等价于 $S_r \oplus S_{l-1} = 0$，即 $S_r = S_{l-1}$。
5. 计数问题： 问题转化为：在序列 $S_0, S_1, \dots, S_n$ 中，有多少对下标 $(i, j)$ 满足 $0 \le i < j \le n$ 且 $S_i = S_j$。 这可以通过遍历数组，用一个计数数组记录每个 mask 出现的次数来快速求解。对于当前位置的 $S_k$，如果它之前出现过 $c$ 次，那么以 $k$ 结尾的合法区间就有 $c$ 个。

C++ 代码实现

#include <iostream>
#include <vector>

using namespace std;

// 30以内的质数，共10个
const int primes[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};

// 计算数值 val 对应的状态掩码
// 第 i 位为 1 代表第 i 个质数的指数为奇数
int get_mask(int val) {
    int mask = 0;
    for (int i = 0; i < 10; ++i) {
        int p = primes[i];
        if (val < p) break; 
        int count = 0;
        while (val % p == 0) {
            count++;
            val /= p;
        }
        if (count % 2 == 1) {
            mask |= (1 << i);
        }
    }
    return mask;
}

int main() {
    // 优化 I/O 效率
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    if (cin >> n) {
        // cnt[mask] 记录前缀异或和 mask 出现的次数
        // mask 最大为 2^10 - 1 = 1023，开 1024 大小足够
        vector<int> cnt(1024, 0);
        
        // S_0 = 0，初始状态
        cnt[0] = 1;
        
        int current_mask = 0;
        long long ans = 0;
        
        for (int i = 0; i < n; ++i) {
            int a;
            cin >> a;
            int mask = get_mask(a);
            
            // 更新当前的前缀异或和
            current_mask ^= mask;
            
            // 如果 current_mask 之前出现过 k 次
            // 那么存在 k 个前缀索引 j < i，使得 S_j = S_i
            // 每一个这样的 j 都对应一个合法的区间 (j+1, i+1)
            ans += cnt[current_mask];
            
            // 记录当前 mask 出现的次数
            cnt[current_mask]++;
        }
        
        cout << ans << endl;
    }
    return 0;
}