【Codeforces 653G】Move by Prime

  由于每个质数之间的操作是相互独立的，所以把每个质数分开考虑。把每个数都质因子分解一遍，时间复杂度是$O(n \sqrt{n})$。

  官方的题解没有讲完，至今不知道它的从k个数到k+1个数是怎么转移的...

  对于质数p，第i个数可表示成$t_i=p^{a_i} \cdot k$的形式，其中k与p互质，然后将数组a排序。

  接下来要做的就是从数组a中选出一些数，进行最少的+1,-1的操作使得选出的这些数最终相等。

  显然，我们要让选出的数最终都等于它们的中位数的时候操作次数最少。

  例如，当我们选出的数为$b_1,b_2,b_3, \cdots ,b_m$时，最少操作次数等于 $$\sum_{i=1}^{mid-1}{b_{mid}-b_i} +\sum_{i=mid+1}^{m}{b_i-b_{mid}}$$

  容易发现，一个数的贡献等于它被加上的次数减去它被减去的次数，乘以这个数本身的值。

  接下来要算的就是一个数最终被加上和减去了多少次。

  考虑$a_k$，如果在$a_k$左边有l个数，在$a_k$右边有r个数，那么

      1.当l<r时，$a_k$对答案贡献次数+1

      2.当l>r时，$a_k$对答案贡献次数-1

      3.当l=r时，$a_k$就是中位数，而且加减次数正好抵消，所以对答案没有贡献。

  思路比较清晰了，计算$a_k$的贡献，就是计算选k左边的数大于和小于k右边的数的方案个数，然后再乘上$a_k$。

  考虑这样一个多项式： $$(1+x)^{k-1} \cdot (1+x^{-1})^{n-k} = \frac{(1+x)^{n-1}}{x^{n-k}}$$

  利用组合的想法，结果的多项式中x的指数即l-r的值，x指数为正即l>r，系数则表示方案数。

  然后可以得到第k个数对答案的贡献为 $$a_k \cdot (C_{n-1}^{n-1}+C_{n-1}^{n-2}+ \cdots +C_{n-1}^{n-k+1} -C_{n-1}^{n-k-1} - C_{n-1}^{n-k-2} - \cdots - C_{n-1}^{0})$$

  最后把一些质数的质数相同的项合并起来瞎JB优化一下就好了。