【20181031T1】一串数字【分解质因数+贪心】

时间:2023-12-17 14:31:02

题面

【错解】

立方就是所有质因子次数都是3的倍数嘛

发现1e5的三次根很小,可以枚举所有和这个数乘起来是完全立方数的(flag*1)

然后……连条边跑最大独立集?

不对啊是NP问题(实际上是个二分图)

那多半要优化连边变成一棵树(flag*2)

推了0.5h没一点结果,就暴搜,希望能剪点枝(那么大的数据剪个*的枝)

然后……搜挂了!0pts

【正解】

既然只和%3有关,那我们可以分解质因数时直接%掉

这样和一个数配对的数是唯一的

由于有重复的数(%了之后),我们可以把它们合并。如果原来是完全立方,就选一个最大的(不能选多个);否则把所有的加起来

然后每对数贪心选最大的

代码