题解：B4398 [蓝桥杯青少年组国赛 2025] 第三题

~~说点题外话：当时蓝桥杯我只过了第一题~~
看到这题，首先就想到了dp解法，这道题和有一道 dp 非常像，但这个要求是乘法。
我们先来看完全平方数的定义：
完全平方数：一个整数，它可以表示为另一个整数的平方。例如，

36

是一个完全平方数，因为

36 = 6 \times 6

。
题目要求每两个数两两相乘的积为完全平方数，也就是说，因子必须成双成对的出现。
那既然牵扯到了因子，为什么不考虑分解质因数呢？
分解质因数可以很好的处理因子数量和因子的问题。
普通的分解质因数肯定是不行了，数据范围一看就知道了。那就只有一个办法：先用线性筛筛出来质数，再分解质因数。线性筛不会可移步至此。

线性筛代码

CPP

//d[i]表示为 i 的质因子
void init(){
    for (int i = 2; i <= M; i++){
        if (!d[i]) p.push_back(i), d[i] = i; //如果是质数，放入p数组中
        for (int j = 0; p[j] <= M / i; j++){
            d[p[j] * i] = p[j];
            if (i % p[j] == 0) break;
        }
    }
}

线性筛的代码可能比普通的不一样，请好好理解。
我们筛出来了

i

的因子，分解质因数也就好写了。
因为要求为两两相乘的完全平方数，我们就可以忽略掉完全平方数因子。
证明一下：
因为要求乘积为完全平方数，举两个数的例子：

18 = 2 \times 3 \times 3

8 = 2 \times 2 \times 2

\begin{aligned} 18 \times 8 &= 2 \times 2 \times 2 \times 2 \times 3 \times 3 \\ &= 2^4 \times 3^2 \end{aligned}

为完全平方数。
若忽略掉因子，则：

18

最终转化为

2

8

最终转化为

2

相乘得

4 = 2^2

，与不去掉因子结果一致，也是完全平方数。
也就是说，可以忽略完全平方数因子。
那我们就可以在分解质因数过程中处理。
具体看代码吧。

AC代码

CPP

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
const int M = 1e7 + 5;
int a[N], d[M], c[M];
vector<int> p;
void init(){
    for (int i = 2; i <= M; i++){
        if (!d[i]) p.push_back(i), d[i] = i;
        for (int j = 0; p[j] <= M / i; j++){
            d[p[j] * i] = p[j];
            if (i % p[j] == 0) break;
        }
    }
}
int main(){
    int n, res = 0;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    init();
    vector<int> v(M);
    for (int i = 1; i <= n; i++){
        int ans = 1;
        while (a[i] > 1){
            if (ans % d[a[i]] == 0) ans /= d[a[i]];
            else ans *= d[a[i]];
            a[i] /= d[a[i]];
        }
        v[ans]++;
        res = max(res, v[ans]);
    }
    printf("%d", res);
    return 0;
}

如有错误地方敬请读者指出。

题解：B4398 [蓝桥杯青少年组国赛 2025] 第三题

文章操作

相关推荐

评论

题解：B4398 [蓝桥杯青少年组国赛 2025] 第三题