组队排位赛13 2020 Petrozavodsk Winter Camp, Jagiellonian U Contest

题解 (opens new window)

Gym 102576A 数学 思维*

题意：给定排列$n$，即${1,2,3,\cdots,n}$。

将数字两两匹配包装（每份包装的价格为1），使得每个配对的最大公因子大于1，未配对的数字单独包装。

求小的花费。

题解：

设配对数为$k$，那么答案为$(n-2k)+k=n-k$

对于素数$v>\lceil\frac{n}{2}\rceil$，只能单独包装（无法配对），因而设$D(n)=大于\lceil\frac{n}{2}\rceil的素数个数$，有上界$k\le\lfloor\frac{n-D(n)}{2}\rfloor$

把数字按其最大质因子分类，假设某一类对应的质因子为$p$，若其大小为偶数，则可以完全匹配，否则，我们让$2p$不参与类内的匹配，并尝试与其他类中剩余的元素进行匹配。

以上方法得到的$k$等于$\lfloor\frac{n-D(n)}{2}\rfloor$

问题转变为：如何求区间$[l,2l]$内的质数个数，这部分内容见我的笔记素数计数问题

Gym 102576B *

Gym 102576C *

Gym 102576D *

Gym 102576E *

Gym 102576F *

Gym 102576G *

Gym 102576H *

Gym 102576I *

Gym 102576J *

Gym 102576K *