首发题解，庆祝一下

大家好，我是энтджей，今天是我2026年第十五次正式发题解！

2026年发布的题解！

能不能点个赞

---

首先简化题意：

• 就是给定一个数组$a$，求 $\prod_{i=l}^{r} a_i是完全平方数$ 的个数

然后就是写代码

• 处理输入（read）：

  • 正常输入

• 核心部分（process）：

  • 暴力枚举，会TLE
  • 那么只能运用一些不同于枚举的方法了：
    • 利用完全平方数的特点：指数都为偶数
    • 那么我们只需要记录底数出现的奇偶性（利用$ ^= 1$），看看这种情况出现的次数，算出一共有多少种不同的 $l,r$ 满足$\prod_{i=l}^{r} a_i是完全平方数$
    • 但为什么记录底数出现的奇偶性就彳亍了呢？
      • 来分析完全平方数的特点：
        • 设一个完全平方数为$y$，则$y$的两个且仅这两个相同的因数为$sqrt(y)$，设$sqrt(y)$为$x$，即$x × x = y$
        • $x = p^{a_1}_1 × p^{a_2}_2 × p^{a_3}_3 × \cdots$
        • 则 :

          $$x \times x = (p_1^{a_1} \times p_2^{a_2} \times p_3^{a_3} \times \cdots) \times (p_1^{a_1} \times p_2^{a_2} \times p_3^{a_3} \times \cdots) = p_1^{2a_1} \times p_2^{2a_2} \times p_3^{2a_3} \times \cdots$$

        • 一个数乘以2一定是偶数（$2a_i$），所以完全平方数仅仅需要看TA的所有（没意识到，错了好几次）质因数的指数是否都为偶数。反过来，如果一个数的所有质因子指数都是偶数，那它也一定是完全平方数（把每个指数除以2，就得到平方根）。

• 最后输出（write）：

  • 正常输出

完整代码：

#include<bits/stdc++.h>
#define int long long  
using namespace std;
const int N = 1024 + 10;

int n;
int primes[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29}; //数据说明了到30就停鸟
int cnt[N];
int ans = 0;
void ReadProcess() {
    cin >> n;
    int mask = 0;
    cnt[0] = 1;
    for(int i = 1; i <= n; i++){
        int x;
        cin >> x;
        for(int j = 0; j < 10; j++) {
            int p = primes[j];
            int exponent  = 0;
            while(x % p == 0){
                exponent ^= 1;
                x /= p;
            }
            if(exponent) {
                mask ^= (1 << j);
            }
        }
        ans += cnt[mask];
        cnt[mask]++;
    }
}
void write() {
    cout << ans;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);

    ReadProcess();
    write();
    return 0;
}
//代码蛮短的

---

🎉完结撒花🎉

怎么感觉这篇又长又短捏？