2020牛客NOIP赛前集训营-普及组（第二场）D变换

这道题据出题人所说出锅了，而赛后改了题面，这里就提供一种原题面的正解，已经出题人证实。

【原题面】
给出一个序列 $A$ ，其中第 $i$ 个数字为 $a_i$ ，你每次有两种操作：

1、选择一个数字不变，将其他数字全部乘以 $x$ 。其中 $x$ 为任意素数。

2、选择一个数字不变，选出其他数字中的一个公共素因子 $x$ ，并将这些数字全部除以 $x$ 。

无需考虑这些数字在变换过程中是否超过 long long 的存储范围。请回答：最少经过多少次操作，可以使得序列中所有数字全部相同。

【题解】

我的思路是，「除去某个数整体 $\pm1$ 」其实等价于将那个数 $\mp1$ ，然后还是把每个质因子分开处理。然后根据一个经典结论：

$\arg\min_x\sum_{s\in S}|x-s|=median(S)$

所以分别处理出中位数即可。

$code$ ：
代码

图片说明