J - Weird Sanchola （贪心)

我们思考一下最终的素数取什么最优，假设素数 $P$P，有 $L$L个元素小于等于 $P$P,有 $R$R个元素大于 $P$P,
那么我们需要移动的次数就显然是 $P\ast (L-R)-su{m}_{\le p}+su{m}_{\>p}$P∗(L−R)−sum≤p​+sum>p​，我们需要最小化这个值.
先将数组按从大到小排序。
结论：当 $n$n为偶数时， $L=R$L=R时最优， $n$n为奇数时， $\mid L-R\mid =1$∣L−R∣=1最优。
证明： $n$n为偶数时，假设 $L\>R$L>R，
$x=L-R\>0$x=L−R>0
$P\ast x-su{m}_{1-L}+su{m}_{L+1-n}$P∗x−sum1−L​+sumL+1−n​
$=su{m}_{L+1-n}-su{m}_{1-\frac{n}{2}}+P\ast x-su{m}_{\frac{n}{2}+1-L}$=sumL+1−n​−sum1−2n​​+P∗x−sum2n​+1−L​
$=su{m}_{\frac{n}{2}+1-n}-su{m}_{1-\frac{n}{2}}+P\ast \frac{x}{2}-su{m}_{\frac{n}{2}+1-L}+P\ast \frac{x}{2}-su{m}_{\frac{n}{2}+1-L}$=sum2n​+1−n​−sum1−2n​​+P∗2x​−sum2n​+1−L​+P∗2x​−sum2n​+1−L​
很显然后面的 $P\ast \frac{x}{2}-su{m}_{\frac{n}{2}+1-L}+P\ast \frac{x}{2}-su{m}_{\frac{n}{2}+1-L}\ge 0$P∗2x​−sum2n​+1−L​+P∗2x​−sum2n​+1−L​≥0
即得到 $su{m}_{\frac{n}{2}+1-n}-su{m}_{1-\frac{n}{2}}\le P\ast x-su{m}_{1-L}+su{m}_{L+1-n}$sum2n​+1−n​−sum1−2n​​≤P∗x−sum1−L​+sumL+1−n​
证毕。
其他情况类似讨论。
然后就是找一个最中间的素数了，直接排完序预处理前缀和后，在中间的数包含的一个区间找素数然后去一个最小答案即可，区间要在保证复杂度的情况下尽量大，区间太小可能找不到最优解。
复杂度 $O(len\ast sqrt(x\left)\right)$O(len∗sqrt(x))

F - Drawing cards （期望)

显然最终桌上的卡片只有 $n$n种可能,
然后我们讨论每种可能的概率：
只有一张的时候显然我们第一次就拿了1，概率为 $\frac{1}{n}$n1​
两张的时候，我们最后一次拿的是1，前面至少1次拿了别的卡片，然后由于后边再拿这种卡片对桌上卡数没有影响，所以我们可以拿无数次，即概率为 ${\sum }_{i=1}^{\infty }(\frac{1}{n}{)}^i=1$∑i=1∞​(n1​)i=1。
类似可得任意可能的概率都是1
然后答案就是 $1-n$1−n的等差数列求和再除 $n$n