GESP 题解库 / 7 级题解 / [GESP202406 七级] 区间乘积 · 第 15 / 24 题
GESP202406 七级 · P10724 · 困难

区间乘积

完全平方 ⟺ 每个质数的指数都是偶数;用 10 位奇偶掩码 + 前缀异或,把"区间积是平方"变成"两个前缀相等"。

🔢
1 ≤ aᵢ ≤ 30
值域极小
🧩
10 位掩码
奇偶性压缩
⚡
O(n)
时间复杂度
🎯
前缀异或 + 哈希计数
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

小杨有一个包含 n 个正整数的序列 A = [a₁, a₂, …, aₙ]。

小杨想知道有多少对 ⟨l, r⟩(1 ≤ l ≤ r ≤ n)满足 aₗ × aₗ₊₁ × … × aᵣ 为完全平方数。

一个正整数 x 为完全平方数,当且仅当存在一个正整数 y 使得 x = y × y。

第一行一个正整数 n;第二行 n 个正整数 aᵢ。输出满足要求的 ⟨l, r⟩ 数量。

💡
人话翻译:把一段连续的数乘起来,看结果是不是某个整数的平方。
不要去算乘积本身——1 ≤ aᵢ ≤ 30 时区间长度可以到 10⁵,真实的乘积会有几万位,根本存不下!
换个角度:一个数是完全平方数,等价于它分解质因数后每个质数的指数都是偶数。幂的指数在乘法中相加,而"偶 + 偶 = 偶、奇 + 奇 = 偶",所以只关心每个质数指数奇偶性的翻转就够了。
由于 aᵢ ≤ 30,涉及的质数只有 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 共 10 个,奇偶性正好用一个 10 位二进制数(掩码)表示。

🔍 关键词提取

完全平方数质因数指数奇偶性前缀异或掩码哈希表计数

已知条件

项目说明
输入第一行 n;第二行 n 个正整数 aᵢ
输出满足"区间乘积为完全平方数"的区间个数
数据范围1 ≤ n ≤ 10⁵,1 ≤ aᵢ ≤ 30
质数集合≤ 30 的质数恰好 10 个 → 掩码只需 10 个二进制位
答案规模上限 C(10⁵ + 1, 2) ≈ 5 × 10⁹ → 必须 long long

需要解决的问题

02
思维导图
整理解题思路的全貌
🧩 奇偶性 → 掩码 → 前缀异或 → 数相等
① 关键转化
完全平方 ⟺ 每个质数的指数都是偶数
乘法 → 指数相加
"偶数"在 mod 2 意义下就是 0
问题 = 区间异或和是否为 0
② 掩码构造
质数只有 2,3,5,7,11,13,17,19,23,29
第 i 位 = 第 i 个质数指数的奇偶性
mask(aᵢ) = 分解后各指数 mod 2
例:4 = 2² → 指数 2 是偶数 → mask = 0
③ 前缀异或
pre[0] = 0(空前缀,必须有)
pre[i] = pre[i−1] xor mask(aᵢ)
区间 (l, r) 合法 ⟺ pre[r] = pre[l−1]
把区间问题变成"两点相等"
④ 计数
哈希表统计每个 pre 值出现次数
答案 = Σ C(cnt[mask], 2)
最多只有 2¹⁰ = 1024 种 mask
答案要用 long long
03
样例手算推导
样例 3 2 4 3 2 的逐步推演

🧮 样例:n = 5,A = [3, 2, 4, 3, 2],答案 2

先把 10 个质数与二进制位的对应关系固定下来,再逐个把 aᵢ 拆开、算出掩码和前缀异或。

质数2357111317192329
对应位b₀b₁b₂b₃b₄b₅b₆b₇b₈b₉
位权1248163264128256512
1
第 1 步:逐个算掩码 mask(aᵢ)

a₁ = 3 = 3¹ → 只有 3 的指数是奇数 → mask = 2(b₁)

a₂ = 2 = 2¹ → 只有 2 的指数是奇数 → mask = 1(b₀)

a₃ = 4 = 2² → 指数 2 是偶数 → mask = 0(所有位都是 0)

a₄ = 3 = 3¹ → mask = 2

a₅ = 2 = 2¹ → mask = 1

✅ 掩码序列 2, 1, 0, 2, 1

2
第 2 步:前缀异或

pre[0] = 0(空前缀)

pre[1] = 0 xor 2 = 2

pre[2] = 2 xor 1 = 3

pre[3] = 3 xor 0 = 3 ← 4 的掩码是 0,所以没变

pre[4] = 3 xor 2 = 1

pre[5] = 1 xor 1 = 0

✅ pre = 0, 2, 3, 3, 1, 0

3
第 3 步:统计每个 pre 值出现次数

pre 值 0 出现 2 次(pre[0]、pre[5])→ C(2,2) = 1

pre 值 3 出现 2 次(pre[2]、pre[3])→ C(2,2) = 1

pre 值 2 出现 1 次、pre 值 1 出现 1 次 → 各 0

合计 1 + 1 = 2

✅ 答案 2

📊 把两个合法区间还原出来

相等的前缀对对应区间 (l, r)乘积是否为完全平方
pre[0] = pre[5] = 0(1, 5)3 × 2 × 4 × 3 × 2 = 144 = 12²✓ 是
pre[2] = pre[3] = 3(3, 3)4 = 2²✓ 是
🔑
两个易被忽略的细节:① pre[0] = 0 必须计入计数——它代表"从第 1 个元素开始"的区间;
② 下标为 i 和 j(i < j)的两个相等前缀,对应的区间是 (i + 1, j),所以 pre[0] = pre[5] 对应区间 (1, 5)。
答案公式 Σ C(cnt[mask], 2) 天然把所有合法区间一次数清。

🧮 全部 15 个区间逐一枚举,反向验证

为了确认"完全平方"这个判定没有疏漏,把所有 5 + 10 = 15 个区间都算一遍(乘积很小,可以硬算)。

区间乘积完全平方?区间乘积完全平方?
(1,1)3✗(2,5)2 × 4 × 3 × 2 = 48✗
(2,2)2✗(3,4)4 × 3 = 12✗
(3,3)4 = 2²✓(3,5)4 × 3 × 2 = 24✗
(4,4)3✗(4,5)3 × 2 = 6✗
(5,5)2✗(1,5)144 = 12²✓
(1,2)6✗(2,3)8✗
(1,3)24✗(2,4)24✗
(1,4)72✗(3,3)4 = 2²✓
1
数一数

打 ✓ 的只有 (3,3) 和 (1,5) 两个

与"前缀异或相等"得到的结果完全一致

注意 4 虽然自身是平方,但它的掩码是 0,所以在 pre 里"什么都不改",这正是它被正确计数的原因

✅ 两种方法互相印证

⚠️
为什么不能直接算乘积?n = 10⁵、aᵢ 全取 30 时,真实乘积是一个约 10⁵ × log₁₀30 ≈ 1.5 × 10⁵ 位的天文数字,任何整数类型都装不下。
而且"判断大整数是否为完全平方"本身也很昂贵。用掩码把"是否平方"压缩成"10 位奇偶性是否为全 0",是这个解法最漂亮的一步。
04
解法对比
前缀异或掩码 O(n) vs 枚举区间 + 维护指数

⚔️ 解法对比

🟢 前缀异或掩码 + 哈希计数(推荐) 推荐

把每个 aᵢ 压成 10 位奇偶掩码,前缀异或后统计"相等的对数"

  • 时间 O(n) 期望
  • 空间 O(min(n, 1024))
  • 核心代码不到 15 行
  • 天然避免大整数运算
💡
最多只有 1024 种前缀值:因为掩码只有 10 位,所以哈希表里最多 1024 个不同的 key。
这意味着你甚至可以不用哈希表,直接开一个长度 1024 的计数数组,把"期望 O(1)"变成"严格 O(1)"。

🟠 枚举左右端点 + 维护质数指数

枚举 l,向右扩展 r,用一个 10 维数组维护指数奇偶性,全偶就计数

  • 时间 O(n²) 或 O(n² × 10)
  • 思路朴素、容易想到
  • n = 10⁵ 时约 5 × 10⁹ 次
  • 只能拿子任务的部分分
⚠️
它其实就是正确解法"多带一个 l"的版本:固定 l 向右扫的同时维护异或值,当异或值回到 0 时就说明区间合法。
把"固定 l 扫描"改成"全局前缀",就得到了 O(n) 的正解——这一步是本题的胜负手。

📈 性能对比

方案复杂度代码量
前缀异或掩码 + 计数O(n)约 25 行
前缀异或掩码 + 1024 数组O(n) 严格约 25 行
枚举端点维护指数O(n² × 10)⚠️ 只有部分分
05
算法流程图
一次扫描构造前缀异或,再统计相等对数
开始:读入 n 与序列 a预处理 mask[1..30]:第 i 位 = 第 i 个质数指数的奇偶性pre = 0;cnt[pre] = 1(空前缀 pre[0] 也要算)对当前 aᵢ:pre = pre xor mask[aᵢ];cnt[pre] += 1n 个数都扫描完了吗?答案 = Σ C(cnt[mask], 2)(遍历所有出现过的前缀值)输出答案(long long)继续下一个数
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🧩 区间乘积完全平方计数

第一行输入 n,第二行输入 n 个 1 ~ 30 的整数。程序会列出每个数的质因数分解、奇偶掩码与前缀异或,并统计有多少对前缀相等。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码(10 位奇偶掩码 + 前缀异或 + 计数数组)

#include <bits/stdc++.h>
using namespace std;

int primes[10] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
int maskOf[31];          // maskOf[v] = v 的"指数奇偶性"掩码
long long cnt[1024];     // 掩码只有 10 位 → 最多 1024 种前缀值

int main() {
    // 预处理 1 ~ 30 的掩码:第 i 位 = 第 i 个质数指数的奇偶性
    for (int v = 1; v <= 30; v++) {
        int ms = 0, t = v;
        for (int i = 0; i < 10; i++) {
            int c = 0;
            while (t % primes[i] == 0) { t /= primes[i]; c++; }
            if (c % 2 == 1) ms |= (1 << i);
        }
        maskOf[v] = ms;
    }

    int n;
    scanf("%d", &n);

    int pre = 0;
    cnt[pre] = 1;               // 空前缀 pre[0] = 0,必须先计入
    for (int i = 0; i < n; i++) {
        int a;
        scanf("%d", &a);
        pre ^= maskOf[a];       // 只翻转"指数奇偶性"
        cnt[pre]++;             // 记录这个前缀值又出现了一次
    }

    long long ans = 0;
    for (int m = 0; m < 1024; m++) {
        long long c = cnt[m];
        ans += c * (c - 1) / 2; // 同一前缀值里任取两个 → 恰好对应一个合法区间
    }
    printf("%lld\n", ans);
    return 0;
}
🔑
为什么计数数组开 1024 就够?前缀值是"10 位掩码",取值范围只有0 ~ 2¹⁰ − 1 = 1023,一共 1024 种可能。
所以可以用定长数组代替哈希表,既不用担心 unordered_map 被卡,又让最后一步统计变成严格的 O(1024)。这是"值域极小"带来的第二重红利。

📖 关键几行怎么看

代码作用为什么这样写
while (t % primes[i] == 0) { t /= primes[i]; c++; }分解质因数统计第 i 个质数的指数,只用看它 mod 2
if (c % 2 == 1) ms |= (1 << i);写掩码指数为奇数才置位;指数为偶数则这一位保持 0
cnt[pre] = 1(初始)空前缀少了这一句,所有从 1 开始的合法区间都会漏掉
pre ^= maskOf[a];前缀异或乘法 → 指数相加 → 奇偶性翻转 = 异或
ans += c * (c − 1) / 2;计数同一 pre 值出现 c 次 → C(c, 2) 个合法区间
long long ans类型答案上限约 5 × 10⁹,int 会溢出
⚠️
四个坑:① 忘记把 pre[0] = 0 计入(漏掉所有以 1 开头的区间);② 用 int 存答案(上限 5 × 10⁹,会溢出成负数);③ 试图直接乘出区间乘积(10⁵ 个数相乘会得到十几万位的数,存不下);④ 误以为"每个 aᵢ 都得是完全平方数"——题目问的是乘积,只要"合起来"每个质数指数为偶就行。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
5
3 2 4 3 2
2题面样例
1
1
11 = 1²,单个区间 (1,1) 合法
1
2
02 不是完全平方数
2
2 2
12 × 2 = 4,只有 (1,2) 合法
3
1 1 1
6全是 1,任意区间乘积都是 1 = 1²
4
4 9 25 1
10每个数都是完全平方,掩码全为 0
3
2 3 6
1只有 (1,3):2 × 3 × 6 = 36 = 6²
2
30 30
130 = 2 × 3 × 5 掩码为 111,两个 111 异或为 0
5
2 3 5 7 210
1210 = 2 × 3 × 5 × 7,(1,5) 乘积 = 44100 = 210²
4
2 4 4 2
4掩码 1,0,0,1:单个 4 各算一个,外加 (1,4) 与 (2,3)
✅
自查清单:① 掩码只留 10 位吗?② pre[0] = 0 计入了吗?③ 答案用 long long 吗?④ 最后是"对每种前缀值求 C(cnt,2) 再求和"吗?

🚨 易错点清单

⚠️
漏掉空前缀:cnt[0] 必须初始化为 1,否则所有 l = 1 的合法区间都会被漏掉。
⚠️
用 int 存答案:答案上限约 5 × 10⁹,必须 long long。
⚠️
直接算乘积:10⁵ 个 ≤ 30 的数相乘是十几万位的大整数,完全无法存储,必须走"奇偶掩码"这条路。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(n)
空间复杂度
O(1024) = O(1)
n 最大
10⁵
答案上限
约 5 × 10⁹

时间怎么算的?

空间都用在哪?

只有一个长度 1024 的 long long 计数数组,即 1024 × 8 B = 8 KB,与 n 无关(即 O(1) 额外空间)。
序列本身也可以边读边处理,不需要存下来。

✅ 总运算量约 10⁵ 次异或,比 O(n²) 的枚举端点快了 5 个数量级;而且空间只有 8 KB,是本题最优雅的解法。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 1) 预处理:把 1 ~ 30 压成"指数奇偶性"掩码(10 位)
int primes[10] = {2,3,5,7,11,13,17,19,23,29};
int maskOf[31];
for (int v = 1; v <= 30; v++) {
    int ms = 0, t = v;
    for (int i = 0; i < 10; i++) {
        int c = 0;
        while (t % primes[i] == 0) { t /= primes[i]; c++; }
        if (c % 2 == 1) ms |= (1 << i);     // 只关心奇偶
    }
    maskOf[v] = ms;                          // 例:maskOf[4] = 0,maskOf[30] = 0b111
}

// 2) 前缀异或:区间积为平方 ⟺ pre[r] == pre[l-1]
long long cnt[1024] = {0};
int pre = 0;
cnt[pre] = 1;                                // 空前缀 pre[0],千万别漏!
for (int i = 0; i < n; i++) { int a; scanf("%d", &a); pre ^= maskOf[a]; cnt[pre]++; }

// 3) 计数:同一前缀值里任取两个下标 → 恰好一个合法区间
long long ans = 0;
for (int m = 0; m < 1024; m++) ans += cnt[m] * (cnt[m] - 1) / 2;

// 4) 对照:若 a_i 的范围放大到 1e9,"10 位掩码"就不够用了
//    此时可给每个质数分配一个随机 64 位整数 h(p),
//    用 pre ^= h(p)(指数为奇数次时)代替位掩码 —— 随机异或哈希

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
质因数指数奇偶性把"是否平方"变成"指数是否全偶"完全平方数判定、平方自由数、整除性判断
状态压缩成掩码10 个质数 → 10 个二进制位状态压缩 DP、集合运算、位运算加速
前缀异或区间信息 = 两个前缀的差区间异或和、区间内出现次数奇偶、前缀和思想
哈希计数配对统计 pre[r] == pre[l−1] 的对数和为 0 的子数组、相等子串、配对计数
🌟
思考题:如果 aᵢ 的范围放大到 10⁹ 甚至 10¹⁸,"10 位掩码"这招就不灵了(涉及的质数可能成百上千,掩码装不下),怎么办?
(提示:仍然只需要"记下每个质数指数的奇偶性",只不过这个向量太长。此时可以给每个质数 p 预先分配一个随机的 64 位整数 h(p),把"向量相加"换成"XOR 异或",于是 pre 依然是一个 64 位整数,照样只要数"有多少对前缀相等"。这就是经典的"随机异或哈希":用概率把高维向量压成一维,出错概率约为 配对数 ÷ 2⁶⁴,实际可以忽略。)