• 测试点 $1\sim 3$ ： $N\le 500,K = 2, A_i \le 10^5​$ 。 暴力枚举两个元素,然后求 $GCD$ 即可,时间复杂度 $O(N^2logW)​$ ，期望得分 $30$ 。

§ 测试点4\sim 54∼5:N\le 500,A_i \le 10^5​N​≤500,A​i​≤105

首先我们从大到小考虑枚举答案，当我们枚举到一个答案xx的时候,我们只要判断xx的倍数是否存在超过kk个即可.** **很显然可以暴力枚举所有的数,然后用xx试除.

复杂度:O(NW)​O​(​NW​),期望得分:5050.

§ 测试点6\sim 86∼8:N\le 10^5,A_i\le 10^8​N​≤105,A​i​≤108 上一档中，我们复杂度的瓶颈在于试除，我们改用其他做法以优化这个复杂度. 我们可以构造一个数组B_iB​i​,表示ii的倍数有多少个.我们考虑在输 入的时候直接对每一个A_iA​i​进行试除,然后直接在相应的约数处修改。最后从大到小遍历B_iB​i​,找出答案.

复杂度:O(N\sqrt{M})​O​(NM​),期望得分80.

§ 测试点9\sim 109∼10:N\le 10^6,A_i \le 10^6​N​≤106,A​i​≤106 A_iA​i​的值域不大，我们可以借助桶的做法.** **显然B_i=\sum_{j=1}^{\dfrac{10^6}{i}}A_{i\times j}B​i​=∑​j​=1i106​​A​​i​×j​.我们发现，预处理好桶以后，直接按照这 个式子计算就是\sum_{i=1}^N\lfloor\frac{N}{i}\rfloor=NlogN∑​i​=1N​⌊iN​⌋=NlogN的时间复杂度.