A15718 | Serval and Music Game
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
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$.
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$ .
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$.
- $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$.
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？
提交通过
评测结果：Accepted