#P13009. 【MX-X13-T4】「KDOI-12」好胜是人的本能,功利是社会的本性。

    ID: 12720 Type: RemoteJudge 2000ms 512MiB Tried: 0 Accepted: 0 Difficulty: 4 Uploaded By: Tags>动态规划 DP贪心O2优化整除分块梦熊比赛

【MX-X13-T4】「KDOI-12」好胜是人的本能,功利是社会的本性。

题目描述

给定一个长度为 nn 的正整数序列 a1,,ana_1, \ldots, a_n 以及一个正整数 mm 满足 mmaxaim \ge \max a_i

你可以对序列进行任意次操作(也可以不操作)。每次操作你可以选择一个区间 [l,r][l,r],然后对于所有 lirl\leq i\leq r,令 aimaia_i\gets\bigl\lfloor\frac{m}{a_i}\bigr\rfloor

求可以得到的 j=1naj\sum_{j=1}^na_j 的最大值以及对应的最少操作次数。

输入格式

本题有多组测试数据。

第一行,一个正整数 TT,表示测试数据组数。对于每组测试数据:

  • 第一行,两个正整数 n,mn,m
  • 第二行,nn 个正整数 a1,,ana_1, \ldots, a_n

输出格式

对于每组测试数据,一行,两个非负整数,分别表示 j=1naj\sum_{j=1}^na_j 的最大值以及对应的最少操作次数。

3
2 5
1 2
5 10
1 5 2 4 3
10 10
1 4 2 5 1 6 2 7 1 10
7 1
28 3
80 5

提示

【样例解释】

对于样例的第二组测试数据:选择以下 33[l,r][l,r] 即可得到最大值 2828

  • [1,2][1,2]
  • [2,5][2,5]
  • [4,5][4,5]

可以证明该方案是最优的之一。

【数据范围】

本题使用捆绑测试。

子任务编号 分值 nn\leq n\sum n\leq 特殊性质
11 99 44 400400
22 2727 10310^3 10410^4
33 1111 10510^5 10610^6 A
44 1616 B
55 3737
  • 特殊性质 A:aima_i\leq\sqrt m
  • 特殊性质 B:aima_i\mid m

对于所有数据:1T1051\leq T\leq 10^51n1051\leq n\leq 10^51n1061\leq\sum n\leq10^61aim10121\leq a_i\leq m\leq10^{12}