Codeforces Round 853 (Div. 2) |
---|
Finished |
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$$$.
431 2 441 2 7 94344208 591000 4779956 540342951633 1661 1741 2134 2221
26 158 758737625 12334970
For the first test case, $$$s_n=4$$$, $$$f(x)$$$ are calculated as followings:
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:
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$$$.
Name |
---|