Remainder Problem (Codeforces 1207F)
Tags: Implement, data structures

You are given an array $$$a$$$ consisting of $$$500000$$$ integers (numbered from $$$1$$$ to $$$500000$$$). Initially all elements of $$$a$$$ are zero.You have to process two types of queries to this array:  $$$1$$$ $$$x$$$ $$$y$$$ — increase $$$a_x$$$ by $$$y$$$;  $$$2$$$ $$$x$$$ $$$y$$$ — compute $$$\sum\limits_{i \in R(x, y)} a_i$$$, where $$$R(x, y)$$$ is the set of all integers from $$$1$$$ to $$$500000$$$ which have remainder $$$y$$$ modulo $$$x$$$. Can you process all the queries?

Input: The first line contains one integer $$$q$$$ ($$$1 \le q \le 500000$$$) — the number of queries.Then $$$q$$$ lines follow, each describing a query. The $$$i$$$-th line contains three integers $$$t_i$$$, $$$x_i$$$ and $$$y_i$$$ ($$$1 \le t_i \le 2$$$). If $$$t_i = 1$$$, then it is a query of the first type, $$$1 \le x_i \le 500000$$$, and $$$-1000 \le y_i \le 1000$$$. If $$$t_i = 2$$$, then it it a query of the second type, $$$1 \le x_i \le 500000$$$, and $$$0 \le y_i < x_i$$$.It is guaranteed that there will be at least one query of type $$$2$$$.

Output: For each query of type $$$2$$$ print one integer — the answer to it.


Sample Inputs:
5
1 3 4
2 3 0
2 4 3
1 4 -4
2 1 0

Sample Outputs:
4
4
0

Solution (Python):
def main():
    q = int(input())
    a = [0] * 500001
    queries = []
    THRESHOLD = 400
    ans = []
    changes_for_small_x = [0] * (THRESHOLD * THRESHOLD + 5)
    for _ in range(q):
        (z, x, y) = readIntArr()
        queries.append((z, x, y))
        if z == 1:
            a[x] += y
            for x2 in range(1, THRESHOLD):
                y2 = x % x2
                changes_for_small_x[x2 * THRESHOLD + y2] += y
        elif x >= THRESHOLD:
            v = 0
            for i in range(y, 500001, x):
                v += a[i]
            ans.append(v)
        else:
            ans.append(changes_for_small_x[x * THRESHOLD + y])
    final_ans = [x for x in ans if x is not None]
    multiLineArrayPrint(final_ans)
    return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
    print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
    print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
    print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
    return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
    dv = defaultValFactory
    da = dimensionArr
    if len(da) == 1:
        return [dv() for _ in range(da[0])]
    else:
        return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(a, b):
    print('? {} {}'.format(a, b))
    sys.stdout.flush()
    return int(input())

def answerInteractive(ans):
    print('! {}'.format(ans))
    sys.stdout.flush()
inf = float('inf')
from math import gcd, floor, ceil
import math
for _abc in range(1):
    main()

Solution (Python):
from collections import Counter

def main():
    q = int(input())
    a = [0] * 500001
    queries = []
    THRESHOLD = 500
    ans = []
    changes_for_small_x = [0] * (THRESHOLD * THRESHOLD + 5)
    for _ in range(q):
        (z, x, y) = readIntArr()
        queries.append((z, x, y))
        if z == 1:
            a[x] += y
            for x2 in range(1, THRESHOLD):
                y2 = x % x2
                changes_for_small_x[x2 * THRESHOLD + y2] += y
        elif x >= THRESHOLD:
            v = 0
            for i in range(y, 500001, x):
                v += a[i]
            ans.append(v)
        else:
            ans.append(changes_for_small_x[x * THRESHOLD + y])
    final_ans = [x for x in ans if x is not None]
    multiLineArrayPrint(final_ans)
    return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
    print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
    print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
    print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
    return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
    dv = defaultValFactory
    da = dimensionArr
    if len(da) == 1:
        return [dv() for _ in range(da[0])]
    else:
        return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(a, b):
    print('? {} {}'.format(a, b))
    sys.stdout.flush()
    return int(input())

def answerInteractive(ans):
    print('! {}'.format(ans))
    sys.stdout.flush()
inf = float('inf')
from math import gcd, floor, ceil
import math
for _abc in range(1):
    main()

Solution (Python):
import sys
n = 500001
sqrt = int(0.75 * n ** 0.5)
data = [0] * n
ans = [[]]
out = []
for i in range(1, sqrt):
    ans.append([0] * i)
j = int(sys.stdin.readline())
qus = sys.stdin.readlines()
for qu in qus:
    q = [int(i) for i in qu.split()]
    if q[0] == 1:
        x = q[1]
        y = q[2]
        data[x] += y
        for i in range(1, sqrt):
            ans[i][x % i] += y
    elif q[1] < sqrt:
        out.append(str(ans[q[1]][q[2]]))
    else:
        sm = 0
        for i in range(q[2], n, q[1]):
            sm += data[i]
        out.append(str(sm))
sys.stdout.write('\n'.join(out) + '\n')