专栏文章

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

LLionBlaze
B4398题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio2g39b
此快照首次捕获于
2025/12/02 12:16
3 个月前
此快照最后确认于
2025/12/02 12:16
3 个月前
查看原文
看起来挺难是不是？首先我们知道这里子序列等价于子集（可重集）。
完全平方数的性质：质因子分解后，每个指数都是偶数。即 n 为完全平方数  ⟺  n=∏p∈Ppαp,∀p∈P,αp≡0(mod2)\displaystyle n\text{ 为完全平方数}\iff n=\prod_{p\in \mathbb P} p^{\alpha_p},\forall p\in \mathbb P,\alpha_p\equiv 0\pmod 2。
两个元素的乘积为完全平方数又等价于他们质因子分解中每个指数的奇偶性都相同。也就是说，将指数模二之后相同。
这样我们就可以把每个数字变为其指数模二之后的数字，然后求众数（出现次数最多的数字）。
转换代码：
CPP
int qaq(int x)
{
    int res = 1;
    for (int i = 2; i * i <= x; i++)
    {
        if (x % i == 0)
        {
            int cnt = 0;
            while (x % i == 0)
            {
                x /= i;
                cnt++;
            }
            if (cnt & 1) res *= i;
        }
    }
    return res * x;
}
计数因为值域比较大（不过 10710^7 也不会爆炸），可以使用 unordered_map。
记录。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...