Pairwise Modulo
Contest: Harbour.Space Scholarship Contest 2021-2022 (open for everyone, rated, Div. 1 + Div. 2)
Difficulty rating: 2300
Tags: data structures, math

You have an array $$$a$$$ consisting of $$$n$$$ distinct positive integers, numbered from $$$1$$$ to $$$n$$$. Define $$$p_k$$$ as $$$$$$p_k = \sum_{1 \le i, j \le k} a_i \bmod a_j,$$$$$$ where $$$x \bmod y$$$ denotes the remainder when $$$x$$$ is divided by $$$y$$$. You have to find and print $$$p_1, p_2, \ldots, p_n$$$.

Input format:
The first line contains $$$n$$$ — the length of the array ($$$2 \le n \le 2 \cdot 10^5$$$).

The second line contains $$$n$$$ space-separated distinct integers $$$a_1, \ldots, a_n$$$ ($$$1 \le a_i \le 3 \cdot 10^5$$$, $$$a_i \neq a_j$$$ if $$$i \neq j$$$).

Output format:
Print $$$n$$$ integers $$$p_1, p_2, \ldots, p_n$$$.

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

Example input:
4
6 2 7 3

Example output:
0 2 12 22

Example input:
3
3 2 1

Example output:
0 3 5

Editorial:
First of all, we have to get rid of the mod operation. The following formula helps very much: $$$x \bmod y = x - y \cdot \lfloor \frac{x}{y} \rfloor$$$.
Since the sum is hard to deal with, we will divide it into two separate sums $$$s_k$$$ and $$$t_k$$$ defined as:
$$$$$$s_k = \sum_{1 \le i, j \le k, i > j} (a_i \bmod a_j),$$$$$$ $$$$$$t_k = \sum_{1 \le i, j \le k, i < j} (a_i \bmod a_j).$$$$$$
How to calculate $$$s_k$$$? Well, we know that $$$s_k = s_{k-1} + \sum_{i=1}^{k-1} (a_k \bmod a_i) = s_{k-1} + \sum_{i=1}^{k-1} (a_k - a_i \cdot \lfloor \frac{a_k}{a_i} \rfloor)$$$. Take $$$a_k$$$ out of the sum and you get $$$s_k = s_{k-1} + a_k \cdot (k-1) - \sum_{i=1}^{k-1} (a_i \cdot \lfloor \frac{a_k}{a_i} \rfloor)$$$.
So, it is still not clear how to calculate it fast. Let's turn things around. Fix some arbitrary $$$a_i$$$ and try to calculate its contribution to all $$$s_k$$$ where $$$k > i$$$.
1. For all $$$a_k$$$ in range $$$[a_i, 2 \cdot a_i)$$$ the contribution is $$$-a_i$$$.
2. For all $$$a_k$$$ in range $$$[2 \cdot a_i, 3 \cdot a_i)$$$ the contribution is $$$-2 \cdot a_i$$$.
3. ...
4. For all $$$a_k$$$ in range $$$[d \cdot a_i, (d+1) \cdot a_i)$$$ the contribution is $$$-d \cdot a_i$$$.
This means we can just brute force all reasonable $$$d$$$ and perform updates of the kind: add $$$x$$$ to all numbers in range $$$[l, r]$$$ which is clearly possible using segment tree or Fenwick tree which allows range updates and point queries.
The only question is: how fast is this? Denote $$$M$$$ as $$$3 \cdot 10^5$$$. Remember the constraint that all $$$a_i$$$ are distinct? It means in the worst-case scenario we will have $$$\frac{M}{1} + \ldots + \frac{M}{n} = M \cdot (\frac{1}{1} + \ldots + \frac{1}{n})$$$ updates. The summation inside the brackets is known as a Harmonic number which is bounded by $$$O(\log n)$$$. So we have $$$O(M \log n)$$$ updates. Each update takes $$$O(\log M)$$$ time, thus the overall time to calculate $$$s_k$$$ is $$$O(M \log M \log n)$$$.
Not bad. Will we be able to calculate $$$t_k$$$ with the same efficiency though? Well, the only difference between $$$s_k$$$ and $$$t_k$$$ is the order of indices, so the solution should be almost the same, right? Exactly. But this time, instead of having range updates and point queries, we will have to deal with point updates and range queries.
Let's get into details. $$$t_k = t_{k-1} + \sum_{i=1}^{k-1} (a_i \bmod a_k) = t_{k-1} + \sum_{i=1}^{k-1} (a_i - a_k \cdot \lfloor \frac{a_i}{a_k} \rfloor)$$$. Separate $$$a_i$$$ and you get $$$t_k = t_{k-1} + \sum_{i=1}^{k-1}a_i - \sum_{i=1}^{k-1} (a_k \cdot \lfloor \frac{a_i}{a_k} \rfloor)$$$.
Almost the same thing. This time, we will go over all multiples of $$$a_k$$$:
1. All $$$a_i$$$ in range $$$[a_k, 2 \cdot a_k)$$$ contribute $$$-a_k$$$.
2. All $$$a_i$$$ in range $$$[2 \cdot a_k, 3 \cdot a_k)$$$ contribute $$$-2 \cdot a_k$$$.
3. ...
4. All $$$a_i$$$ in range $$$[d \cdot a_k, (d+1) \cdot a_k)$$$ contribute $$$-d \cdot a_k$$$.
It should be crystal clear by now that we are dealing with point updates and range queries here. The time complexity is the same.
So, in total we get $$$O(M \log M \log n)$$$ time complexity and $$$O(n + M)$$$ space complexity. Be careful with segment trees, though. Using the classical recursive segment tree with pushes will probably result in a big constant and time out. Just remember that we are not dealing with advanced stuff there, so there is no need for pushes.