完全平方 ⟺ 每个质数的指数都是偶数;用 10 位奇偶掩码 + 前缀异或,把"区间积是平方"变成"两个前缀相等"。
小杨有一个包含 n 个正整数的序列 A = [a₁, a₂, …, aₙ]。
小杨想知道有多少对 ⟨l, r⟩(1 ≤ l ≤ r ≤ n)满足 aₗ × aₗ₊₁ × … × aᵣ 为完全平方数。
一个正整数 x 为完全平方数,当且仅当存在一个正整数 y 使得 x = y × y。
第一行一个正整数 n;第二行 n 个正整数 aᵢ。输出满足要求的 ⟨l, r⟩ 数量。
完全平方数质因数指数奇偶性前缀异或掩码哈希表计数
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 n;第二行 n 个正整数 aᵢ |
| 输出 | 满足"区间乘积为完全平方数"的区间个数 |
| 数据范围 | 1 ≤ n ≤ 10⁵,1 ≤ aᵢ ≤ 30 |
| 质数集合 | ≤ 30 的质数恰好 10 个 → 掩码只需 10 个二进制位 |
| 答案规模 | 上限 C(10⁵ + 1, 2) ≈ 5 × 10⁹ → 必须 long long |
pre[i] = mask(a₁) xor mask(a₂) xor … xor mask(aᵢ),并令 pre[0] = 0。那么区间 (l, r) 的异或和 = pre[r] xor pre[l − 1],它等于 0 ⟺ pre[r] == pre[l − 1]。于是答案就是"有多少对下标上的前缀值相等",用哈希表数一数即可:Σ C(cnt[mask], 2)先把 10 个质数与二进制位的对应关系固定下来,再逐个把 aᵢ 拆开、算出掩码和前缀异或。
| 质数 | 2 | 3 | 5 | 7 | 11 | 13 | 17 | 19 | 23 | 29 |
|---|---|---|---|---|---|---|---|---|---|---|
| 对应位 | b₀ | b₁ | b₂ | b₃ | b₄ | b₅ | b₆ | b₇ | b₈ | b₉ |
| 位权 | 1 | 2 | 4 | 8 | 16 | 32 | 64 | 128 | 256 | 512 |
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
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
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 + 1, j),所以 pre[0] = pre[5] 对应区间 (1, 5)。Σ C(cnt[mask], 2) 天然把所有合法区间一次数清。为了确认"完全平方"这个判定没有疏漏,把所有 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² | ✓ |
打 ✓ 的只有 (3,3) 和 (1,5) 两个
与"前缀异或相等"得到的结果完全一致
注意 4 虽然自身是平方,但它的掩码是 0,所以在 pre 里"什么都不改",这正是它被正确计数的原因
✅ 两种方法互相印证
10⁵ × log₁₀30 ≈ 1.5 × 10⁵ 位的天文数字,任何整数类型都装不下。把每个 aᵢ 压成 10 位奇偶掩码,前缀异或后统计"相等的对数"
枚举 l,向右扩展 r,用一个 10 维数组维护指数奇偶性,全偶就计数
| 方案 | 复杂度 | 代码量 |
|---|---|---|
| 前缀异或掩码 + 计数 | O(n) | 约 25 行 |
| 前缀异或掩码 + 1024 数组 | O(n) 严格 | 约 25 行 |
| 枚举端点维护指数 | O(n² × 10) | ⚠️ 只有部分分 |
第一行输入 n,第二行输入 n 个 1 ~ 30 的整数。程序会列出每个数的质因数分解、奇偶掩码与前缀异或,并统计有多少对前缀相等。
点按钮开始 →
#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; }
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ᵢ 都得是完全平方数"——题目问的是乘积,只要"合起来"每个质数指数为偶就行。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
5 | 2 | 题面样例 |
1 | 1 | 1 = 1²,单个区间 (1,1) 合法 |
1 | 0 | 2 不是完全平方数 |
2 | 1 | 2 × 2 = 4,只有 (1,2) 合法 |
3 | 6 | 全是 1,任意区间乘积都是 1 = 1² |
4 | 10 | 每个数都是完全平方,掩码全为 0 |
3 | 1 | 只有 (1,3):2 × 3 × 6 = 36 = 6² |
2 | 1 | 30 = 2 × 3 × 5 掩码为 111,两个 111 异或为 0 |
5 | 1 | 210 = 2 × 3 × 5 × 7,(1,5) 乘积 = 44100 = 210² |
4 | 4 | 掩码 1,0,0,1:单个 4 各算一个,外加 (1,4) 与 (2,3) |
pre[0] = 0 计入了吗?③ 答案用 long long 吗?④ 最后是"对每种前缀值求 C(cnt,2) 再求和"吗?cnt[0] 必须初始化为 1,否则所有 l = 1 的合法区间都会被漏掉。long long。C(cnt, 2):O(1024)只有一个长度 1024 的 long long 计数数组,即 1024 × 8 B = 8 KB,与 n 无关(即 O(1) 额外空间)。
序列本身也可以边读边处理,不需要存下来。
✅ 总运算量约 10⁵ 次异或,比 O(n²) 的枚举端点快了 5 个数量级;而且空间只有 8 KB,是本题最优雅的解法。
// 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 的子数组、相等子串、配对计数 |
pre 依然是一个 64 位整数,照样只要数"有多少对前缀相等"。这就是经典的"随机异或哈希":用概率把高维向量压成一维,出错概率约为 配对数 ÷ 2⁶⁴,实际可以忽略。)