310150: CF1789E. Serval and Music Game
Memory Limit：256 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Serval and Music Game
题意翻译
### 题目描述 给定整数 $n$ 和长度为 $n$ 的**递增**序列 $s$。 定义 $f(x)$ 为满足下列要求的整数 $i(1\leq i\leq n)$ 的数量： - 存在**非负整数** $p_i,q_i$ 使得 $s_i=p_i\bigg\lfloor\dfrac{s_n}{x}\bigg\rfloor+q_i\bigg\lceil\dfrac{s_n}{x}\bigg\rceil$。 你需要求出 $\sum_{x=1}^{s_n}x\times f(x)$ 对 $998244353$ 取模后的值。 每个测试点包含 $t$ 组数据。 ### 输入格式 第一行输入一个整数 $t(1\leq t\leq10^4)$ 表示数据组数，接下来对于每组数据： 第一行输入一个整数 $n(1\leq n\leq10^6)$。 接下来输入一行 $n$ 个整数表示序列 $s(1\leq s_1<s_2<\cdots<s_n\leq10^7)$。 单个测试点内所有组数据对应的 $n$ 之和不超过 $10^6$，对应的 $s_n$ 之和不超过 $10^7$。 ### 输出格式 对于每组数据： 输出一行一个整数表示 $\sum_{x=1}^{s_n}x\times f(x)$ 对 $998244353$ 取模后的值。题目描述
Serval loves playing music games. He meets a problem when playing music games, and he leaves it for you to solve. You are given $ n $ positive integers $ s_1 < s_2 < \ldots < s_n $ . $ f(x) $ is defined as the number of $ i $ ( $ 1\leq i\leq n $ ) that exist non-negative integers $ p_i, q_i $ such that: $$ s_i=p_i\left\lfloor{s_n\over x}\right\rfloor + q_i\left\lceil{s_n\over x}\right\rceil $$ Find out $ \sum_{x=1}^{s_n} x\cdot f(x)$ modulo $ 998\,244\,353 $ . As a reminder, $ \lfloor x\rfloor $ denotes the maximal integer that is no greater than $ x $ , and $ \lceil x\rceil $ denotes the minimal integer that is no less than $x$.输入输出格式
输入格式
Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1\leq t\leq 10^4 $ ). The description of the test cases follows. The first line of each test cases contains a single integer $ n $ ( $ 1\leq n\leq 10^6 $ ). The second line of each test case contains $ n $ positive integers $ s_1,s_2,\ldots,s_n $ ( $ 1\leq s_1 < s_2 < \ldots < s_n \leq 10^7 $ ). It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^6 $ , and the sum of $ s_n $ does not exceed $ 10^7 $ .
输出格式
For each test case, print a single integer in a single line — the sum of $ x\cdot f(x) $ over all possible $ x $ modulo $ 998\,244\,353 $ .
输入输出样例
输入样例 #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说明
For the first test case, $ s_n=4 $ , $ f(x) $ are calculated as followings: - $ f(1)=1 $ - $ \left\lfloor s_n\over 1\right\rfloor=4 $ , $ \left\lceil s_n\over 1\right\rceil=4 $ . - It can be shown that such $ p_1,p_2 $ and $ q_1,q_2 $ that satisfy the conditions don't exist. - Let $ p_3=1 $ and $ q_3=0 $ , then $ 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 $ . - It can be shown that such $ p_1 $ and $ q_1 $ that satisfy the conditions don't exist. - Let $ p_2=1 $ and $ q_2=0 $ , then $ 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 $ . - Let $ p_3=0 $ and $ q_3=2 $ , then $ 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 $ . - Let $ p_1=1 $ and $ q_1=0 $ , then $ 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 $ . - Let $ p_2=0 $ and $ q_2=1 $ , then $ 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 $ . - Let $ p_3=0 $ and $ q_3=2 $ , then $ 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 $ . - Let $ p_1=1 $ and $ q_1=0 $ , then $ 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 $ . - Let $ p_2=1 $ and $ q_2=1 $ , then $ 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 $ . - Let $ p_3=2 $ and $ q_3=2 $ , then $ 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 $ . Therefore, the answer is $ \sum_{x=1}^4 x\cdot f(x) = 1\cdot 1 + 2\cdot 2 + 3\cdot 3 + 4\cdot 3 = 26 $ . For the second test case: - $ f(1)=f(2)=f(3)=1 $ - $ f(4)=3 $ - $ f(5)=f(6)=f(7)=f(8)=f(9)=4 $ For example, when $ x=3 $ we have $ f(3)=1 $ because there exist $ p_4 $ and $ q_4 $ : $$ 9 = 1 \cdot\left\lfloor{9\over 3}\right\rfloor + 2 \cdot\left\lceil{9\over 3}\right\rceil $$ It can be shown that it is impossible to find $ p_1,p_2,p_3 $ and $ q_1,q_2,q_3 $ that satisfy the conditions. When $ x=5 $ we have $ f(5)=4 $ because there exist $ p_i $ and $ q_i $ as followings: $$ 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 $$ Therefore, the answer is $ \sum_{x=1}^9 x\cdot f(x) = 158$.Input
题意翻译
### 题目描述 给定整数 $n$ 和长度为 $n$ 的**递增**序列 $s$。 定义 $f(x)$ 为满足下列要求的整数 $i(1\leq i\leq n)$ 的数量： - 存在**非负整数** $p_i,q_i$ 使得 $s_i=p_i\bigg\lfloor\dfrac{s_n}{x}\bigg\rfloor+q_i\bigg\lceil\dfrac{s_n}{x}\bigg\rceil$。 你需要求出 $\sum_{x=1}^{s_n}x\times f(x)$ 对 $998244353$ 取模后的值。 每个测试点包含 $t$ 组数据。 ### 输入格式 第一行输入一个整数 $t(1\leq t\leq10^4)$ 表示数据组数，接下来对于每组数据： 第一行输入一个整数 $n(1\leq n\leq10^6)$。 接下来输入一行 $n$ 个整数表示序列 $s(1\leq s_1<s_2<\cdots<s_n\leq10^7)$。 单个测试点内所有组数据对应的 $n$ 之和不超过 $10^6$，对应的 $s_n$ 之和不超过 $10^7$。 ### 输出格式 对于每组数据： 输出一行一个整数表示 $\sum_{x=1}^{s_n}x\times f(x)$ 对 $998244353$ 取模后的值。Output
**题目大意：**
题目描述了一个游戏，其中涉及一个序列 $ s $ 和一个函数 $ f(x) $ 的定义。给定一个长度为 $ n $ 的递增序列 $ s $，对于每个 $ x $ 的值，函数 $ f(x) $ 是满足特定条件的整数 $ i $ 的数量，这些条件涉及到序列 $ s $ 的最后一个元素 $ s_n $ 以及非负整数 $ p_i, q_i $，使得 $ s_i $ 可以表示为 $ s_n $ 除以 $ x $ 的向下取整和向上取整的线性组合。需要计算的是 $\sum_{x=1}^{s_n} x \times f(x)$ 对 $ 998244353 $ 取模的结果。
**输入输出数据格式：**
输入格式：
- 第一行包含一个整数 $ t $，表示数据组数，$ t $ 的范围是 $ 1 \leq t \leq 10^4 $。
- 接下来每组数据的第一行包含一个整数 $ n $，表示序列 $ s $ 的长度，$ n $ 的范围是 $ 1 \leq n \leq 10^6 $。
- 每组数据的第二行包含 $ n $ 个整数，表示序列 $ s $ 的元素，这些元素是递增的，并且范围是 $ 1 \leq s_1 < s_2 < \ldots < s_n \leq 10^7 $。
输出格式：
- 对于每组数据，输出一行一个整数，表示 $\sum_{x=1}^{s_n} x \times f(x)$ 对 $ 998244353 $ 取模后的值。
**LaTeX格式的公式：**
$$
f(x) = \text{满足条件的整数 } i \text{ 的数量，使得存在非负整数 } p_i, q_i \text{，满足 } s_i = p_i\left\lfloor\dfrac{s_n}{x}\right\rfloor + q_i\left\lceil\dfrac{s_n}{x}\right\rceil
$$
$$
\text{需要计算：} \sum_{x=1}^{s_n} x \times f(x) \text{ 对 } 998244353 \text{ 取模}
$$
其中，$ \lfloor x \rfloor $ 表示不超过 $ x $ 的最大整数，$ \lceil x \rceil $ 表示不小于 $ x $ 的最小整数。**题目大意：** 题目描述了一个游戏，其中涉及一个序列 $ s $ 和一个函数 $ f(x) $ 的定义。给定一个长度为 $ n $ 的递增序列 $ s $，对于每个 $ x $ 的值，函数 $ f(x) $ 是满足特定条件的整数 $ i $ 的数量，这些条件涉及到序列 $ s $ 的最后一个元素 $ s_n $ 以及非负整数 $ p_i, q_i $，使得 $ s_i $ 可以表示为 $ s_n $ 除以 $ x $ 的向下取整和向上取整的线性组合。需要计算的是 $\sum_{x=1}^{s_n} x \times f(x)$ 对 $ 998244353 $ 取模的结果。 **输入输出数据格式：** 输入格式： - 第一行包含一个整数 $ t $，表示数据组数，$ t $ 的范围是 $ 1 \leq t \leq 10^4 $。 - 接下来每组数据的第一行包含一个整数 $ n $，表示序列 $ s $ 的长度，$ n $ 的范围是 $ 1 \leq n \leq 10^6 $。 - 每组数据的第二行包含 $ n $ 个整数，表示序列 $ s $ 的元素，这些元素是递增的，并且范围是 $ 1 \leq s_1 < s_2 < \ldots < s_n \leq 10^7 $。 输出格式： - 对于每组数据，输出一行一个整数，表示 $\sum_{x=1}^{s_n} x \times f(x)$ 对 $ 998244353 $ 取模后的值。 **LaTeX格式的公式：** $$ f(x) = \text{满足条件的整数 } i \text{ 的数量，使得存在非负整数 } p_i, q_i \text{，满足 } s_i = p_i\left\lfloor\dfrac{s_n}{x}\right\rfloor + q_i\left\lceil\dfrac{s_n}{x}\right\rceil $$ $$ \text{需要计算：} \sum_{x=1}^{s_n} x \times f(x) \text{ 对 } 998244353 \text{ 取模} $$ 其中，$ \lfloor x \rfloor $ 表示不超过 $ x $ 的最大整数，$ \lceil x \rceil $ 表示不小于 $ x $ 的最小整数。
题目描述了一个游戏，其中涉及一个序列 $ s $ 和一个函数 $ f(x) $ 的定义。给定一个长度为 $ n $ 的递增序列 $ s $，对于每个 $ x $ 的值，函数 $ f(x) $ 是满足特定条件的整数 $ i $ 的数量，这些条件涉及到序列 $ s $ 的最后一个元素 $ s_n $ 以及非负整数 $ p_i, q_i $，使得 $ s_i $ 可以表示为 $ s_n $ 除以 $ x $ 的向下取整和向上取整的线性组合。需要计算的是 $\sum_{x=1}^{s_n} x \times f(x)$ 对 $ 998244353 $ 取模的结果。
**输入输出数据格式：**
输入格式：
- 第一行包含一个整数 $ t $，表示数据组数，$ t $ 的范围是 $ 1 \leq t \leq 10^4 $。
- 接下来每组数据的第一行包含一个整数 $ n $，表示序列 $ s $ 的长度，$ n $ 的范围是 $ 1 \leq n \leq 10^6 $。
- 每组数据的第二行包含 $ n $ 个整数，表示序列 $ s $ 的元素，这些元素是递增的，并且范围是 $ 1 \leq s_1 < s_2 < \ldots < s_n \leq 10^7 $。
输出格式：
- 对于每组数据，输出一行一个整数，表示 $\sum_{x=1}^{s_n} x \times f(x)$ 对 $ 998244353 $ 取模后的值。
**LaTeX格式的公式：**
$$
f(x) = \text{满足条件的整数 } i \text{ 的数量，使得存在非负整数 } p_i, q_i \text{，满足 } s_i = p_i\left\lfloor\dfrac{s_n}{x}\right\rfloor + q_i\left\lceil\dfrac{s_n}{x}\right\rceil
$$
$$
\text{需要计算：} \sum_{x=1}^{s_n} x \times f(x) \text{ 对 } 998244353 \text{ 取模}
$$
其中，$ \lfloor x \rfloor $ 表示不超过 $ x $ 的最大整数，$ \lceil x \rceil $ 表示不小于 $ x $ 的最小整数。**题目大意：** 题目描述了一个游戏，其中涉及一个序列 $ s $ 和一个函数 $ f(x) $ 的定义。给定一个长度为 $ n $ 的递增序列 $ s $，对于每个 $ x $ 的值，函数 $ f(x) $ 是满足特定条件的整数 $ i $ 的数量，这些条件涉及到序列 $ s $ 的最后一个元素 $ s_n $ 以及非负整数 $ p_i, q_i $，使得 $ s_i $ 可以表示为 $ s_n $ 除以 $ x $ 的向下取整和向上取整的线性组合。需要计算的是 $\sum_{x=1}^{s_n} x \times f(x)$ 对 $ 998244353 $ 取模的结果。 **输入输出数据格式：** 输入格式： - 第一行包含一个整数 $ t $，表示数据组数，$ t $ 的范围是 $ 1 \leq t \leq 10^4 $。 - 接下来每组数据的第一行包含一个整数 $ n $，表示序列 $ s $ 的长度，$ n $ 的范围是 $ 1 \leq n \leq 10^6 $。 - 每组数据的第二行包含 $ n $ 个整数，表示序列 $ s $ 的元素，这些元素是递增的，并且范围是 $ 1 \leq s_1 < s_2 < \ldots < s_n \leq 10^7 $。 输出格式： - 对于每组数据，输出一行一个整数，表示 $\sum_{x=1}^{s_n} x \times f(x)$ 对 $ 998244353 $ 取模后的值。 **LaTeX格式的公式：** $$ f(x) = \text{满足条件的整数 } i \text{ 的数量，使得存在非负整数 } p_i, q_i \text{，满足 } s_i = p_i\left\lfloor\dfrac{s_n}{x}\right\rfloor + q_i\left\lceil\dfrac{s_n}{x}\right\rceil $$ $$ \text{需要计算：} \sum_{x=1}^{s_n} x \times f(x) \text{ 对 } 998244353 \text{ 取模} $$ 其中，$ \lfloor x \rfloor $ 表示不超过 $ x $ 的最大整数，$ \lceil x \rceil $ 表示不小于 $ x $ 的最小整数。