题解：P10724 [GESP202406 七级] 区间乘积

· · 题解

前言

一个月没写题解了，为了挽救估值，精心写了这篇题解。

本文有些冗长，可能会浪费您的时间，但可以对这道题有更清晰的理解。

约定

  1. 下文中 \bigoplus 表示异或。
  2. 质数 p 在 a 中出现了 x 次表示将 a 分解质因数后，p 一共出现了 x 次。

思路

二进制表示

首先，我们把每个数 a_i 分解质因数，显然，a_i 为完全平方数当且仅当每个质数都出现了偶数次。

注意到本题 1\le a_i\le30，其中的质数只有 2,3,5,7,11,13,17,19,23,29，共 10 个。我们不妨将 1\sim30 中每个数用二进制表示：对于第 i 个质数（第 i 位），若它出现了奇数次，这个二进制数的第 i 位为 1，若出现了偶数次，则为 0。

两数相乘的二进制表示

由于本题需要乘法，我们考虑当知道 a 和 b 的二进制表示 x 与 y，如何求出 ab 的二进制表示 z。对于第 i 个质数 p_i，共有四种情况：

容易发现，以上每种情况其实都是在进行异或操作，推出 z=x\bigoplus y。

本题主要部分

对于本题，令 b_i 为 i 的二进制表示，我们要维护一个前缀异或和，也就是 pre_i=\bigoplus_{j=1}^ib_{a_i} 或 pre_i=pre_{i-1}\bigoplus b_{a_i}，特别的，pre_0=0。

容易发现，区间 [l,r] 满足答案当且仅当 pre_r=pre_{l-1}，当 pre_r 和 pre_{l-1} 为 1 的位异或后相互抵消时，[l,r] 中数的乘积才是完全平方数。

令 cnt_i 表示二进制表示为 i 的数的个数。我们从 1\sim n 扫描每个数 a_i，右端点为 i 满足条件的区间的个数为 cnt_{pre_i}，将其计入答案后更新 cnt_{pre_i}。

细节

  2. 先计入答案，后更新（ans += cnt[prexor]++;）。
  4. 十年 OI 一场空，不开 【】 见祖宗！

代码

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

int n, a[100005], b[35], prexor;
long long ans, cnt[1 << 10];
vector <int> prime = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};

void read(int &a, int ch = 0) {
    while (!isdigit(ch = getchar()));
    for (a = 0; isdigit(ch); ch = getchar()) a = (a << 3) + (a << 1) + (ch ^ 48);
}
void prework() {
    // 预处理数组 b
    for (int i = 1; i <= 30; i++) {
        int j = i;
        for (int k = 0; k < 10; k++) {
            while (j % prime[k] == 0) {
                b[i] ^= 1 << k;
                j /= prime[k];
            }
        }
    }
}
int main() {
    prework();
    read(n);
    cnt[0] = 1;
    for (int i = 1; i <= n; i++) {
        read(a[i]);
        prexor ^= b[a[i]];
        ans += cnt[prexor]++;
    }
    cout << ans;
    return 0;
}

写在最后

本题思维难度和代码难度都一般，感觉评绿有点高了，应该是上位黄。

本人表达能力较差，简单的思路被写得很冗长，但将其底层逻辑刨析得较为透彻。

本人写文章偏向学术，有些内容可能晦涩难懂，欢迎在评论区指出。