← 返回题目列表

Codeforces · 1789/E

E. 仆人和音乐游戏

中文机器翻译题面 查看原题

Serval 喜欢玩音乐游戏。他在玩音乐游戏时遇到了问题,他把它留给你来解决。

给你 $$$n$$$ 正整数 $$$s_1 < s_2 < \ldots < s_n$$$。 $$$f(x)$$$ 被定义为存在非负整数 $$$p_i, q_i$$$ 的 $$$i$$$ ($$$1\leq i\leq n$$$) 的数量,使得:

$$$$$$s_i=p_i\left\lfloor{s_n\over x}\right\rfloor + q_i\left\lceil{s_n\over x}\right\rceil$$$$$$

找出 $$$\sum_{x=1}^{s_n} x\cdot f(x)$$$ 模 $$$998\,244\,353$$$。

提醒一下,$$$\lfloor x\rfloor$$$ 表示不大于 $$$x$$$ 的最大整数,$$$\lceil x\rceil$$$ 表示不小于 $$$x$$$ 的最小整数。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1\leq t\leq 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1\leq n\leq 10^6$$$)。

每个测试用例的第二行包含 $$$n$$$ 正整数 $$$s_1,s_2,\ldots,s_n$$$ ($$$1\leq s_1 < s_2 < \ldots < s_n \leq 10^7$$$)。

保证所有测试用例的$$$n$$$总和不超过$$$10^6$$$,并且$$$s_n$$$总和不超过$$$10^7$$$。

输出

对于每个测试用例,在一行中打印一个整数 - 所有可能的 $$$x$$$ 模 $$$998\,244\,353$$$ 的 $$$x\cdot f(x)$$$ 之和。

示例

输入 #1

4
3
1 2 4
4
1 2 7 9
4
344208 591000 4779956 5403429
5
1633 1661 1741 2134 2221

输出 #1

26
158
758737625
12334970

注意

对于第一个测试用例,$$$s_n=4$$$,$$$f(x)$$$计算如下:

- $$$f(1)=1$$$ $$$\left\lfloor s_n\over 1\right\rfloor=4$$$,$$$\left\lceil s_n\over 1\right\rceil=4$$$。 可以证明,满足条件的$$$p_1,p_2$$$和$$$q_1,q_2$$$并不存在。 设 $$$p_3=1$$$ 和 $$$q_3=0$$$,则 $$$s_3 = p_3\cdot\left\lfloor s_n\over 1\right\rfloor + q_3\cdot\left\lceil s_n\over 1\right\rceil = 1\cdot 4 + 0\cdot 4 = 4$$$。
- $$$f(2)=2$$$ $$$\left\lfloor s_n\over 2\right\rfloor=2$$$,$$$\left\lceil s_n\over 2\right\rceil=2$$$。 可以证明,满足条件的$$$p_1$$$和$$$q_1$$$并不存在。 设 $$$p_2=1$$$ 和 $$$q_2=0$$$,则 $$$s_2 = p_2\cdot\left\lfloor s_n\over 2\right\rfloor + q_2\cdot\left\lceil s_n\over 2\right\rceil = 1\cdot 2 + 0\cdot 2 = 2$$$。 设 $$$p_3=0$$$ 和 $$$q_3=2$$$,则 $$$s_3 = p_3\cdot\left\lfloor s_n\over 2\right\rfloor + q_3\cdot\left\lceil s_n\over 2\right\rceil = 0\cdot 2 + 2\cdot 2 = 4$$$。
- $$$f(3)=3$$$ $$$\left\lfloor s_n\over 3\right\rfloor=1$$$,$$$\left\lceil s_n\over 3\right\rceil=2$$$。 设 $$$p_1=1$$$ 和 $$$q_1=0$$$,则 $$$s_1 = p_1\cdot\left\lfloor s_n\over 3\right\rfloor + q_1\cdot\left\lceil s_n\over 3\right\rceil = 1\cdot 1 + 0\cdot 2 = 1$$$。 设$$$p_2=0$$$ 和$$$q_2=1$$$,则$$$s_2 = p_2\cdot\left\lfloor s_n\over 3\right\rfloor + q_2\cdot\left\lceil s_n\over 3\right\rceil = 0\cdot 1 + 1\cdot 2 = 2$$$。 设 $$$p_3=0$$$ 和 $$$q_3=2$$$,则 $$$s_3 = p_3\cdot\left\lfloor s_n\over 3\right\rfloor + q_3\cdot\left\lceil s_n\over 3\right\rceil = 0\cdot 1 + 2\cdot 2 = 4$$$。
- $$$f(4)=3$$$ $$$\left\lfloor s_n\over 4\right\rfloor=1$$$,$$$\left\lceil s_n\over 4\right\rceil=1$$$。 令 $$$p_1=1$$$ 和 $$$q_1=0$$$,则 $$$s_1 = p_1\cdot\left\lfloor s_n\over 4\right\rfloor + q_1\cdot\left\lceil s_n\over 4\right\rceil = 1\cdot 1 + 0\cdot 1 = 1$$$。 设 $$$p_2=1$$$ 和 $$$q_2=1$$$,则 $$$s_2 = p_2\cdot\left\lfloor s_n\over 4\right\rfloor + q_2\cdot\left\lceil s_n\over 4\right\rceil = 1\cdot 1 + 1\cdot 1 = 2$$$。 设 $$$p_3=2$$$ 和 $$$q_3=2$$$,则 $$$s_3 = p_3\cdot\left\lfloor s_n\over 4\right\rfloor + q_3\cdot\left\lceil s_n\over 4\right\rceil = 2\cdot 1 + 2\cdot 1 = 4$$$。

因此,答案是 $$$\sum_{x=1}^4 x\cdot f(x) = 1\cdot 1 + 2\cdot 2 + 3\cdot 3 + 4\cdot 3 = 26$$$。

对于第二个测试用例:

- $$$f(1)=f(2)=f(3)=1$$$
- $$$f(4)=3$$$
- $$$f(5)=f(6)=f(7)=f(8)=f(9)=4$$$

例如,当 $$$x=3$$$ 时,我们有 $$$f(3)=1$$$,因为存在 $$$p_4$$$ 和 $$$q_4$$$:

$$$$$$9 = 1 \cdot\left\lfloor{9\over 3}\right\rfloor + 2 \cdot\left\lceil{9\over 3}\right\rceil$$$$$$

可以证明,不可能找到满足条件的$$$p_1,p_2,p_3$$$和$$$q_1,q_2,q_3$$$。

当$$$x=5$$$时,我们有$$$f(5)=4$$$,因为存在$$$p_i$$$和$$$q_i$$$,如下所示:

$$$$$$1 = 1 \cdot\left\lfloor{9\over 5}\right\rfloor + 0 \cdot\left\lceil{9\over 5}\right\rceil$$$$$$ $$$$$$2 = 0 \cdot\left\lfloor{9\over 5}\right\rfloor + 1 \cdot\left\lceil{9\over 5}\right\rceil$$$$$$ $$$$$$7 = 3 \cdot\left\lfloor{9\over 5}\right\rfloor + 2 \cdot\left\lceil{9\over 5}\right\rceil$$$$$$ $$$$$$9 = 3 \cdot\left\lfloor{9\over 5}\right\rfloor + 3 \cdot\left\lceil{9\over 5}\right\rceil$$$$$$

因此,答案是$$$\sum_{x=1}^9 x\cdot f(x) = 158$$$。