企业官网建设流程全解析

又是信奥刷题打卡的一天。今天刚把洛谷 P6273（eJOI 2017 的 Magic）AC 掉，趁热打铁写一篇完整复盘。这题在洛谷的难度标签不算特别高，但我真心觉得它非常适合用来打通一个经典套路：前缀异或 + 随机哈希 + 统计相等前缀。光看题解就是一瞬间的事，但自己从 TLE 一路调到 WA 再到 AC，踩过的坑比看十篇题解都值。

如果你正在备战信奥，已经能熟练写 C++ 和 STL，但一遇到“区间统计”“奇偶性”“完全平方数”这类题就头皮发麻，那这篇就是写给你的。我会把题目本质、数学转化、工程实现、调试经验全部拆开讲清楚，文末还会给出可直接 AC 的完整代码。看完你会发现，这题表面叫“魔法”，核心其实是一个特别朴素的计数问题。

1. 先看懂题目：魔法子段到底在考什么

1.1 题意翻译与本质

题目大意不复杂：给一个长度为 n 的序列，问有多少个连续子段满足——子段内所有数的乘积是一个完全平方数。

举个例子，序列[2, 3, 6]中：

• 子段[2]，乘积 2，不是平方数，不合法；
• 子段[3]，乘积 3，不是平方数，不合法；
• 子段[6]，乘积 6，不是平方数，不合法；
• 子段[2, 3]，乘积 6，不合法；
• 子段[3, 6]，乘积 18，不合法；
• 子段[2, 3, 6]，乘积 36，是6^2，合法。

所以答案是 1。

这个“乘积是完全平方数”的条件，在质因数分解的世界里有一个非常漂亮的等价说法：对区间内所有数做质因数分解，把每个质数的指数全部加起来，如果每个质数的指数都是偶数，那这个乘积就是完全平方数。

换句话说，我们完全不关心指数具体是多少，只关心指数的奇偶性。偶数就是 0，奇数就是 1。这一下就把一个乘法问题拉到了模 2 的世界里。

1.2 为什么“乘积为平方数”可以变成“异或为 0”

这是整道题最关键的一步推导，我单独拎出来讲。

假设我们给每个质数一个“状态位”，比如质数2对应第 0 位，质数3对应第 1 位，质数5对应第 2 位……那么每个数都可以表示成一个二进制向量，第 k 位表示“这个质数在这个数里出现了奇数次还是偶数次”。奇数记 1，偶数记 0。

于是：

• mask(2)，因为2 = 2^1，只有 2 出现奇数次，向量是000...001；
• mask(3)，向量是000...010；
• mask(6)，因为6 = 2^1 * 3^1，两个质数都出现一次，向量是000...011。

现在关键来了：两个数相乘，对应质数的指数是相加的，而相加之后再看奇偶，其实是异或。也就是说：

mask(a * b) = mask(a) xor mask(b)

这个性质非常重要。它意味着我们可以像处理前缀和一样处理前缀异或。

定义：

pref[i] = mask(a[1]) xor mask(a[2]) xor ... xor mask(a[i])

那么区间[l, r]的乘积向量就是：

pref[r] xor pref[l-1]

如果区间乘积是完全平方数，等价于这个向量全是 0，等价于：

pref[r] xor pref[l-1] = 0 pref[r] = pref[l-1]

所以题目瞬间变成：统计有多少对前缀状态相等。再加一个空前缀pref[0] = 0，答案就是所有相同前缀状态里任选两个的组合数之和。

这就是整道题的核心思路。理解了这一步，这道题你已经会了一半。

2. 从质因数分解到状态压缩

2.1 朴素思考：枚举区间为什么必挂

拿到这种题，第一反应肯定是枚举左右端点，然后对区间内每个数做质因数分解，维护所有质因子的奇偶性。但 n 的范围是 1e5，区间数量就是 n(n+1)/2，大约 5e9 个区间，每个区间还要做质因数分解。这个复杂度无论怎么优化都是不可能过的。

所以必须走前缀这条路。用前缀状态把区间查询变成两个前缀状态的比较，一下子把 O(n^2) 的枚举压缩成 O(n) 的扫描。

但这又带来一个新问题：前缀状态怎么存？

如果质因子种类很少，比如只有 26 个字母那种题，我们用一个 int 的 26 个二进制位就够了。可本题中 ai 最大到 1e9，质因子的种类理论上可能非常多，多到什么程度？一个 1e9 以内的数最多有 9 个左右的不同质因子，但 n 个数完全可以各自贡献一个不同的大质数。也就是说，整个序列里可能出现的不同质因子数量，最坏可以接近 n，也就是 1e5 级别。

用 1e5 个二进制位去表示一个状态？每做一个前缀就要复制一份？内存和时间都会爆炸。所以需要一个聪明的办法把状态压缩成轻量级的 key。

2.2 用哈希压缩质因子奇偶状态

竞赛里处理这种“动态出现、数量未知”的质因子集合，最常用的做法就是随机哈希。

具体做法是：第一次遇到某个质数 p 时，给它随机分配一个 64 位的整数h(p)。然后每个数的 mask 就是它所有出现次数为奇数的质因子的h(p)异或起来。因为异或满足结合律和交换律，所以：

mask(a * b) = mask(a) xor mask(b)

依然成立。就是说，我们不需要老老实实存 1e5 位的向量，只要用一个unsigned long long，就能表示一个前缀的奇偶状态。

前缀计算也变成：

pref[i] = pref[i-1] xor mask(a[i])

统计答案时，用一个unordered_map<unsigned long long, long long>记录每个前缀状态出现过多少次，一边扫描一边累加。整个过程极其干净。

2.3 质因数分解的工程优化：素数表

解决完状态压缩，还有一个隐藏的复杂度坑：质因数分解本身。

如果暴力从 2 试除到 sqrt(x)，也就是最多到 31623，每个数最坏要跑三万多次。n 是 1e5，最坏就是 30 亿次取模，这是必 TLE 的。

正确做法是预处理一个 31623 以内的素数表。31623 以内的质数一共只有大约 3401 个。这样每个数最坏只需要试除 3401 个质数，总次数降到 3.4 亿级别，C++ 能在 1 秒左右跑完，配合快速 IO 才能稳稳通过。

素数表用一个最简单的埃氏筛就行，代码也不长。这一步属于典型的“看着不起眼，不加就 TLE”的工程优化，后面踩坑部分我还会再提。

3. 随机哈希：这道题真正的考点

3.1 为什么不能直接开 bitset 存状态

有人可能会问：既然质因子最多 1e5 种，那我直接用一个bitset<100000>表示状态不行吗？

理论上可以，但实际完全不可行。一个bitset<100000>就是 12.5KB，每个前缀状态都存一份的话，1e5 个前缀就是 1.25GB，内存直接爆炸。就算不全部存下来，只排序比较，排序过程反复复制大 bitset 的时间也是天文数字。

更关键的是，我们根本不知道质因子的总种类数。它是边读入边出现的，你没法在一开始就确定 bitset 的长度。动态扩容的 bitset 又慢又难写。

所以随机哈希几乎是唯一现实的选择。它的本质是用一个极小概率的哈希冲突，换取 O(1) 的状态比较。

3.2 随机哈希原理与冲突分析

给每个质数分配一个 64 位随机数，这里的“随机”必须是真的随机，最好是每次运行都不同。否则如果哈希映射关系固定，出题人可以把数据构造到大量产生碰撞。

为什么随机值就能保证正确性？因为两个不同的奇偶向量，它们的哈希值恰好相等的概率大约是 2^-64。n = 1e5 时，总共有大约 5e9 对前缀状态，碰撞期望数量是：

5e9 / 2^64 ≈ 2.7e-10

这个概率比比赛时电脑断电的概率还低，实际做题完全不需要担心。

当然，如果心里实在过不去，可以用双哈希：给每个质数分配两个独立的 64 位随机值，组成一个pair<ull, ull>作为状态，计数时用map。这样碰撞概率降到 2^-128，属于理论上的“绝对稳妥”。但代价是代码更啰嗦、常数更大。我一般单哈希就够用了。

3.3 稳一点：双哈希方案

双哈希的实现思路很简单：把前面代码里的getHash改成返回两个随机值即可。状态 key 从ull换成pair<ull, ull>，计数容器从unordered_map换成map，或者自定义一个 pair 的 hash。

如果你追求极致的保险，可以这样写：

struct Node { ull a, b; bool operator<(const Node& other) const { return a == other.a ? b < other.b : a < other.a; } bool operator==(const Node& other) const { return a == other.a && b == other.b; } };

然后用map<Node, long long>统计。不过实测单哈希在本题已经非常稳，我最终 AC 的版本就是单哈希。

4. 完整 C++ 代码与逐段解析

4.1 AC 代码（单哈希）

下面是完整可用的 AC 代码，关键部分都加了注释。我建议你先自己抄一遍跑通，再往下看逐段拆解。

#include <bits/stdc++.h> using namespace std; using ull = unsigned long long; // 自定义哈希，防止 unordered_map 被极端数据卡掉 struct CustomHash { static uint64_t splitmix64(uint64_t x) { x += 0x9e3779b97f4a7c15ULL; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL; x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL; return x ^ (x >> 31); } size_t operator()(uint64_t x) const { static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(x + FIXED_RANDOM); } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; // 预先生成 sqrt(1e9) 以内的质数表，加速分解 const int LIM = 31623; vector<bool> isPrime(LIM + 1, true); isPrime[0] = isPrime[1] = false; vector<int> primes; for (int i = 2; i <= LIM; ++i) { if (isPrime[i]) { primes.push_back(i); if (1LL * i * i <= LIM) { for (int j = i * i; j <= LIM; j += i) { isPrime[j] = false; } } } } // 给每个质数随机分配一个 64 位哈希值 mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); unordered_map<int, ull, CustomHash> hashVal; hashVal.reserve(200000); auto getHash = [&](int p) -> ull { auto it = hashVal.find(p); if (it != hashVal.end()) return it->second; ull h = rng(); if (h == 0) h = 1; // 避免哈希值为 0，影响奇偶判断 hashVal[p] = h; return h; }; // 统计前缀状态出现次数，空前缀状态为 0 unordered_map<ull, long long, CustomHash> cnt; cnt.reserve(200000); cnt[0] = 1; long long ans = 0; ull pref = 0; for (int i = 1; i <= n; ++i) { int x; cin >> x; // 对当前数分解质因数，只把指数为奇数的质因子异或进 mask ull cur = 0; for (int p : primes) { if (1LL * p * p > x) break; if (x % p == 0) { int c = 0; while (x % p == 0) { x /= p; ++c; } if (c & 1) cur ^= getHash(p); } } if (x > 1) cur ^= getHash(x); // 更新前缀状态并计数 pref ^= cur; auto it = cnt.find(pref); if (it != cnt.end()) ans += it->second; cnt[pref]++; } cout << ans << '\n'; return 0; }

4.2 关键代码段拆解

第一个值得仔细看的是质因数分解部分。注意我并不是完整记录每个质因子的指数，而是只关心指数是奇数还是偶数。对于指数为偶数的质因子，它的奇偶性是 0，异或上它没有任何影响，所以可以直接跳过。这意味着12 = 2^2 * 3^1产生的cur只会异或hash(3)，而不会异或hash(2)。这样写既节省时间，也避免状态被无关质因子干扰。

第二个关键点是getHash函数里的h == 0特判。随机数生成器理论上可能生成 0，如果某个质数的哈希值是 0，那么这个质数的奇偶性就永远不影响任何状态，严格来说是一个逻辑漏洞。概率极低，但加一行判断成本几乎为零，属于写了不亏的防御性代码。

第三个关键点是计数顺序：

if (it != cnt.end()) ans += it->second; cnt[pref]++;

先累加已经出现过的次数，再把自己加进去，这保证统计的每一对都是i < j的前缀对，不会出现同一个位置和自己配对的情况。如果反过来，答案会凭空多出 n 个。

5. 踩坑实录：从 TLE、WA 到 AC

5.1 为什么会 TLE：分解方式不对

我第一次提交 TLE 得非常冤枉，因为代码逻辑完全正确，问题就出在质因数分解上。

我当时图省事，直接写成：

for (int d = 2; 1LL * d * d <= x; ++d) { ... }

自以为每个数分解时 x 会不断变小，循环能提前 break。但在极端数据下，比如 n = 1e5，所有 ai 都是接近 1e9 的大质数，每个数都要从头试除到 31623，总循环次数接近 30 亿次，TLE 是必然的。

换用素数表之后，同样数据只需要跑约 3.4 亿次，速度提升接近 9 倍，稳稳 AC。

注意：这不是特例。信奥里凡是涉及对多个数做质因数分解的题，第一件事就是考虑要不要预处理素数表。 别等到 TLE 了才想起来。

5.2 为什么会 WA：类型溢出与边界处理

WA 的坑主要集中在三个地方。

第一，答案变量要用long long。n = 1e5 时，全部子段数为 n(n+1)/2 ≈ 5e9，已经超过int的范围。如果忘了开long long，大数据直接爆掉。

第二，剩余质因子的处理。分解完小于 sqrt(x) 的因子后，如果 x 还大于 1，说明剩下的 x 本身是一个大质数，需要单独异或一次getHash(x)。但这里有个反向边界：如果 x 原本就是 1，分解循环直接退出，剩余 x 还是 1，1不是质数，不能异或。所以判断条件必须是if (x > 1)，而不是if (x != 1)。虽然这两种写法在这道题里结果一样，但逻辑上区分清楚能避免在其他题目里犯糊涂。

第三，哈希值为 0 的特殊处理。前文已经提过，随机哈希值如果恰好为 0，会让某个质因子失去作用，导致该质因子出现次数为奇数的区间被误判为合法。虽然概率极低，但在对拍大数据时确实可能成为唯一的 WA 来源。

5.3 哈希冲突到底要不要怕

很多刚开始接触随机哈希的选手会陷入一个焦虑：万一两个不同的状态哈希冲突了怎么办？

我的答案是：单 64 位随机哈希在 OI 常规数据范围内，冲突概率可以忽略不计。你更需要担心的不是哈希冲突，而是unordered_map被卡。

这里说的“被卡”不是指哈希冲突，而是指标准库的unordered_map在遭遇精心构造的 key 分布时，可能退化到接近 O(n^2) 的复杂度。比如某些版本的 STL 内部用取模桶，如果 key 是恶意构造的等差数列，每次查找都可能踩到同一个桶。

解决办法就是自己写一个 CustomHash，把 key 做一次 splitmix64 扰动后再散列。这也是我上面代码里那个看起来很长的结构体的作用。这个技巧在洛谷很多题解里都有，属于竞赛 C++ 选手的必备防身术。

5.4 本地对拍验证模板

随机哈希最怕的不是慢，而是“感觉对了但答案偶尔不对”。所以本地对拍是必须的。

我的对拍思路很简单：写一个 O(n^2) 暴力程序，再写一个随机数据生成器，然后循环跑几百组数据，比较两边的输出。

暴力程序核心就几行：

long long brute(const vector<int>& a) { int n = a.size(); long long ans = 0; for (int l = 0; l < n; ++l) { vector<int> cnt(100, 0); // 只处理小范围数据 for (int r = l; r < n; ++r) { int x = a[r]; for (int p = 2; p * p <= x; ++p) { while (x % p == 0) { x /= p; cnt[p] ^= 1; } } if (x > 1) cnt[x] ^= 1; bool ok = true; for (int v : cnt) if (v) { ok = false; break; } if (ok) ans++; } } return ans; }

生成器就随机生成 n 在 1 到 10、ai 在 1 到 30 的小数据。然后写个脚本循环对拍。如果小数据跑 500 组全对，基本上代码逻辑和哈希安全性就都稳了。

这个对拍习惯强烈建议养成。信奥里很多“看起来对了但交上去 WA”的题，都是靠对拍揪出隐藏 bug 的。

6. 这类题的通法总结与扩展

6.1 套路识别：看到“偶数次/平方数/奇偶性”怎么想

刷题多了你会发现，信息学竞赛特别喜欢把“奇偶性”和“前缀”组合在一起出题。一旦题目里出现这些关键词，脑子里就要立刻拉响警报：

• 出现“每个质因子出现次数为偶数”“乘积为完全平方数”这类说法，先想质因数分解，再想模 2 状态向量；
• 出现“区间统计”，先想能不能用前缀状态把区间变成两个端点的比较；
• 出现“状态数量未知、可能很多”，先想随机哈希；
• 最后，看到“统计相等状态对”，就是C(cnt, 2)累加。

这条链路就是 P6273 的全部骨架。下次再遇到类似的题，哪怕题目换了一层壳，也能快速套上这个思考框架。

6.2 两道同套路变式

这个套路最常见的变式是：

第一，统计一个字符串中有多少子串，使每个字符出现次数都是偶数。因为字符集只有 26 个，所以不用哈希，直接用一个 int 的 26 位当状态，前缀异或之后用数组计数就行。

第二，在本题基础上改条件：统计有多少子段，使得恰好有 k 个质因子的出现次数为奇数。做法是维护前缀哈希状态，然后对每个前缀，去查询它异或上所有“恰好 k 位置为 1”的掩码后得到的值出现过多少次。这个就要用unordered_map配合枚举了，复杂度会多一个组合系数，但思想完全一致。

你看，一个套路吃透，能打一片题。

6.3 我的刷题心得

最后说点个人体会。我做这道题最大的收获，不是学会了随机哈希这个技术点，而是明白了“先推数学，再写代码”的价值。第一次做的时候我直接上手写暴力，写完发现不对；第二次想用 bitset，写完发现内存爆炸；直到我老老实实把“乘积为平方数”翻译成“前缀异或相等”，代码反而半小时就写完了。

动笔之前先想清楚转化关系，永远比盲目调代码省时间。P6273 的“魔法”不在题目本身，而在那个“把所有数的乘积拉回质因数指数奇偶性”的瞬间。你如果也想通了这一点，这题就真的学会了。