Pairwise Modulo (Codeforces 1553F)
Tags: Math, data structures

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: 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: Print $$$n$$$ integers $$$p_1, p_2, \ldots, p_n$$$. 


Sample Inputs:
4
6 2 7 3

3
3 2 1

Sample Outputs:
0 2 12 22

0 3 5

Solution (Python):
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

class fenwick(object):

    def __init__(self, n):
        self.n = n
        self.cul = [0] * n

    def update(self, index, diff):
        i = index
        while i < self.n:
            self.cul[i] += diff
            i += i + 1 & -i - 1

    def getaccu(self, index):
        output = 0
        i = index
        while i >= 0:
            output += self.cul[i]
            i -= i + 1 & -i - 1
        return output

def main():
    n = int(input())
    arr = list(map(int, input().split()))
    maximum = max(arr)
    ans = [0] * n
    nums = fenwick(maximum + 1)
    subtract = fenwick(maximum + 1)
    count = fenwick(maximum + 1)
    tot = 0
    for i in range(n):
        smaller = arr[i] * count.getaccu(arr[i])
        smaller += subtract.getaccu(arr[i])
        larger = tot - nums.getaccu(arr[i])
        num = 2 * arr[i]
        while num <= maximum:
            subtract.update(num, -arr[i])
            larger -= (i - count.getaccu(num - 1)) * arr[i]
            num += arr[i]
        count.update(arr[i], 1)
        nums.update(arr[i], arr[i])
        ans[i] = smaller + larger
        tot += arr[i]
    for i in range(1, n):
        ans[i] += ans[i - 1]
    print(' '.join(map(str, ans)))
main()

Solution (Python):
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

class fenwick(object):

    def __init__(self, n):
        self.n = n
        self.cul = [0] * n

    def update(self, index, diff):
        i = index
        while i < self.n:
            self.cul[i] += diff
            i += i + 1 & -i - 1

    def getaccu(self, index):
        output = 0
        i = index
        while i >= 0:
            output += self.cul[i]
            i -= i + 1 & -i - 1
        return output

def main(t):
    n = int(input())
    arr = list(map(int, input().split()))
    maximum = max(arr)
    ans = [0] * n
    nums = fenwick(maximum + 1)
    subtract = fenwick(maximum + 1)
    count = fenwick(maximum + 1)
    tot = 0
    for i in range(n):
        smaller = arr[i] * count.getaccu(arr[i])
        smaller += subtract.getaccu(arr[i])
        larger = tot - nums.getaccu(arr[i])
        num = 2 * arr[i]
        while num <= maximum:
            subtract.update(num, -arr[i])
            larger -= (i - count.getaccu(num - 1)) * arr[i]
            num += arr[i]
        count.update(arr[i], 1)
        nums.update(arr[i], arr[i])
        ans[i] = smaller + larger
        tot += arr[i]
    for i in range(1, n):
        ans[i] += ans[i - 1]
    print(' '.join(map(str, ans)))
T = 1
t = 1
while t <= T:
    main(t)
    t += 1

Solution (Python):
from sys import stdin, stdout

def bit_update(bit_a, i, v):
    while i < len(bit_a):
        bit_a[i] += v
        i += i & -i

def bit_query(bit_a, i):
    r = 0
    while i > 0:
        r += bit_a[i]
        i -= i & -i
    return r

def bit_range_query(bit_a, l, r):
    return bit_query(bit_a, r) - bit_query(bit_a, l - 1)
n = int(stdin.readline())
a_a = list(map(int, stdin.readline().split()))
N = max(a_a) + 1
bit_a = [0 for _ in range(N * 2)]
bit_a2 = [0 for _ in range(N * 2)]
p_a = [0] * n
ans = sum = 0
for i in range(1, n + 1):
    x = a_a[i - 1]
    ans += x * (i - 1)
    ans += sum
    sum += x
    ans -= bit_query(bit_a, x)
    j = x
    while j < N:
        l = j
        r = l + x - 1
        ans -= bit_range_query(bit_a2, l, r) * j
        bit_update(bit_a, l, x)
        j += x
    bit_update(bit_a2, x, 1)
    p_a[i - 1] = ans
stdout.write(' '.join(map(str, p_a)))