Serval and Music Game (Codeforces 1789E)
Tags: Math, number theory

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$$$.

Input: 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$$$.

Output: 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$$$.

Note: 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$$$.

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

Sample Outputs:
26
158
758737625
12334970

Solution (Python):
import sys
import math
input = sys.stdin.readline
M = 998244353
for __ in range(int(input())):
    n = int(input())
    s = [int(xx) for xx in input().split()]
    ans = 0
    pr = [0] * (s[-1] + 2)
    for i in range(n):
        pr[s[i] + 1] = 1
    for i in range(1, s[-1] + 2):
        pr[i] += pr[i - 1]
    d = {}
    for i in range(n - 1):
        x = math.gcd(s[i], s[-1])
        if x in d:
            ans += d[x]
        else:
            sp = 0
            for j in range(1, int(x ** 0.5) + 1):
                if x % j == 0:
                    sp += s[-1] // j
                    if x // j - j:
                        sp += s[-1] // (x // j)
                    sp %= M
            d[x] = sp
            ans += sp
    sp = 0
    for j in range(1, int(s[-1] ** 0.5) + 1):
        if s[-1] % j == 0:
            sp += j
            if s[-1] // j - j:
                sp += s[-1] // j
            sp %= M
    ans += sp
    z = -1111111
    t = -1111111
    for x in range(1, s[-1] + 1):
        k = s[-1] // x
        if s[-1] % x:
            if z == k:
                ans += t * x
            else:
                sp = n
                for i in range(k):
                    l = i * k + i
                    r = i * k + k - 1
                    if l > s[-1]:
                        break
                    sp -= pr[r + 1] - pr[l + 1]
                z = k
                t = sp
                ans += t * x
            ans %= M
    print(ans % M)

Solution (Python):
import sys
import math
input = sys.stdin.readline
M = 998244353
for __ in range(int(input())):
    n = int(input())
    s = [int(xx) for xx in input().split()]
    ans = 0
    pr = [0] * (s[-1] + 2)
    for i in range(n):
        pr[s[i] + 1] = 1
    for i in range(1, s[-1] + 2):
        pr[i] += pr[i - 1]
    d = {}
    for i in range(n - 1):
        x = math.gcd(s[i], s[-1])
        if x in d:
            ans += d[x]
        else:
            sp = 0
            for j in range(1, int(x ** 0.5) + 1):
                if x % j == 0:
                    sp += s[-1] // j
                    if x // j - j:
                        sp += s[-1] // (x // j)
                    sp %= M
            d[x] = sp
            ans += sp
    sp = 0
    for j in range(1, int(s[-1] ** 0.5) + 1):
        if s[-1] % j == 0:
            sp += j
            if s[-1] // j - j:
                sp += s[-1] // j
            sp %= M
    ans += sp
    z = -1111111
    t = -1111111
    for x in range(1, s[-1] + 1):
        k = s[-1] // x
        if s[-1] % x:
            if z == k:
                ans += t * x
            else:
                sp = n
                for i in range(k):
                    l = i * k + i
                    r = i * k + k - 1
                    if l > s[-1]:
                        break
                    sp -= pr[r + 1] - pr[l + 1]
                z = k
                t = sp
                ans += t * x
            ans %= M
    print(ans % M)

Solution (Python):
import sys
import math
input = sys.stdin.readline
M = 998244353
for __ in range(int(input())):
    n = int(input())
    s = [int(xx) for xx in input().split()]
    ans = 0
    pr = [0] * (s[-1] + 2)
    for i in range(n):
        pr[s[i] + 1] = 1
    for i in range(1, s[-1] + 2):
        pr[i] += pr[i - 1]
    d = {}
    for i in range(n - 1):
        x = math.gcd(s[i], s[-1])
        if x in d:
            ans += d[x]
        else:
            sp = 0
            for j in range(1, int(x ** 0.5) + 1):
                if x % j == 0:
                    sp += s[-1] // j
                    if x // j - j:
                        sp += s[-1] // (x // j)
                    sp %= M
            d[x] = sp
            ans += sp
    sp = 0
    for j in range(1, int(s[-1] ** 0.5) + 1):
        if s[-1] % j == 0:
            sp += j
            if s[-1] // j - j:
                sp += s[-1] // j
            sp %= M
    ans += sp
    z = -1111111
    t = -1111111
    for x in range(1, s[-1] + 1):
        k = s[-1] // x
        if s[-1] % x:
            if z == k:
                ans += t * x
            else:
                sp = n
                for i in range(k):
                    l = i * k + i
                    r = i * k + k - 1
                    if l > s[-1]:
                        break
                    sp -= pr[r + 1] - pr[l + 1]
                z = k
                t = sp
                ans += t * x
            ans %= M
    print(ans % M)