Balance (Easy version) (Codeforces 1732D1)
Tags: Implement, number theory

This is the easy version of the problem. The only difference is that in this version there are no "remove" queries.Initially you have a set containing one element — $$$0$$$. You need to handle $$$q$$$ queries of the following types:+ $$$x$$$ — add the integer $$$x$$$ to the set. It is guaranteed that this integer is not contained in the set; ? $$$k$$$ — find the $$$k\text{-mex}$$$ of the set. In our problem, we define the $$$k\text{-mex}$$$ of a set of integers as the smallest non-negative integer $$$x$$$ that is divisible by $$$k$$$ and which is not contained in the set.

Input: The first line contains an integer $$$q$$$ ($$$1 \leq q \leq 2 \cdot 10^5$$$) — the number of queries.The following $$$q$$$ lines describe the queries.An addition query of integer $$$x$$$ is given in the format + $$$x$$$ ($$$1 \leq x \leq 10^{18}$$$). It is guaranteed that $$$x$$$ was not contained in the set.A search query of $$$k\text{-mex}$$$ is given in the format ? $$$k$$$ ($$$1 \leq k \leq 10^{18}$$$).It is guaranteed that there will be at least one query of type ?.

Output: For each query of type ? output a single integer — the $$$k\text{-mex}$$$ of the set.

Note: In the first example:After the first and second queries, the set will contain elements $$$\{0, 1, 2\}$$$. The smallest non-negative number that is divisible by $$$1$$$ and is not contained in the set is $$$3$$$.After the fourth query, the set will contain the elements $$$\{0, 1, 2, 4\}$$$. The smallest non-negative number that is divisible by $$$2$$$ and is not contained in the set is $$$6$$$.In the second example:   Initially, the set contains only the element $$$\{0\}$$$.  After adding an integer $$$100$$$ the set contains elements $$$\{0, 100\}$$$.  $$$100\text{-mex}$$$ of the set is $$$200$$$.  After adding an integer $$$200$$$ the set contains elements $$$\{0, 100, 200\}$$$.  $$$100\text{-mex}$$$ of the set is $$$300$$$.  After adding an integer $$$50$$$ the set contains elements $$$\{0, 50, 100, 200\}$$$.  $$$50\text{-mex}$$$ of the set is $$$150$$$. 

Sample Inputs:
15
+ 1
+ 2
? 1
+ 4
? 2
+ 6
? 3
+ 7
+ 8
? 1
? 2
+ 5
? 1
+ 1000000000000000000
? 1000000000000000000

6
+ 100
? 100
+ 200
? 100
+ 50
? 50

Sample Outputs:
3
6
3
3
10
3
2000000000000000000

200
300
150

Solution (Python):
import sys
import math

def solve():
    inp = sys.stdin.readline
    q = int(inp())
    s = {0}
    d = {}
    for i in range(q):
        (t, x) = inp().split()
        if t == '+':
            s.add(int(x))
        elif t == '?':
            x = int(x)
            v = d.get(x, 0)
            while v in s:
                v += x
            d[x] = v
            print(v)
        else:
            raise Exception('wut')

def main():
    solve()
if __name__ == '__main__':
    main()

Solution (Python):
import sys
INF = 10 ** 20
MOD = 10 ** 9 + 7
from math import gcd
from math import ceil, log2, factorial
from collections import defaultdict as dd, Counter
from bisect import bisect_left as bl, bisect_right as br

def fastio():
    import sys
    from io import StringIO
    from atexit import register
    global input
    sys.stdin = StringIO(sys.stdin.read())
    input = lambda : sys.stdin.readline().rstrip('\r\n')
    sys.stdout = StringIO()
    register(lambda : sys.__stdout__.write(sys.stdout.getvalue()))
fastio()
I = lambda : list(map(int, input().split()))
TESTS = 0
''

def solve():
    (q,) = I()
    s = set()
    d = dd(int)
    while q:
        q -= 1
        (op, x) = input().split()
        x = int(x)
        if op == '+':
            s.add(x)
        else:
            if d[x] == 0:
                d[x] = x
            while d[x] in s:
                d[x] = d[x] + x
            print(d[x])

def main():
    if not TESTS:
        solve()
        return
    (t,) = I()
    while t:
        solve()
        t -= 1
if __name__ == '__main__':
    main()

Solution (Python):
import bisect
from sys import stdin
input = stdin.readline
mod = 10 ** 9 + 7
eps = 10 ** (-9)

def linp(type=int):
    return list(map(type, input().split()))

def minp(type=int):
    return map(type, input().split())

def tinp(type=int):
    return type(input())

def __gcd(a, b):
    return a if b == 0 else __gcd(b, a % b)

def __lcm(a, b):
    return a * b / __gcd(a, b)

def __fact(n):
    return 1 if n == 1 else n * __fact(n - 1)

def __mex(a):
    mex = 0
    a.sort()
    for x in a:
        if x <= mex:
            mex += 1
        else:
            break
    return mex

def __dist(x1, y1, x2, y2):
    return (x1 - x2) ** 2 + (y1 - y2) ** 2

def __getprimes(n):
    isprime = [True for i in range(n + 1)]
    primes = []
    for i in range(2, n + 1):
        if isprime[i]:
            for j in range(i * i, n + 1, i):
                isprime[j] = False
    for i in range(2, n + 1):
        if isprime[i]:
            primes.append(i)
    return primes

def __getdividers(n):
    i = 1
    ret = []
    while i * i <= n:
        if n % i == 0:
            ret.append(i)
            if i * i != n:
                ret.append(n // i)
        i += 1
    ret.sort()
    return ret

def __modInverse(a, m):
    m0 = m
    y = 0
    x = 1
    if m == 1:
        return 0
    while a > 1:
        q = a // m
        t = m
        m = a % m
        a = t
        t = y
        y = x - q * y
        x = t
    if x < 0:
        x = x + m0
    return x

def __isprime(n):
    if n < 2:
        return False
    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += 1
    return True

def __cntprimediv(n):
    ret = 0
    x = n
    i = 2
    while i * i <= x:
        while n % i == 0:
            n //= i
            ret += 1
        i += 1
    if n > 1:
        ret += 1
    return ret

def __primefactors(n):
    ret = []
    x = n
    i = 2
    while i * i <= x:
        while n % i == 0:
            ret.append(i)
            n //= i
        i += 1
    if n > 1:
        ret.append(n)
    return ret

def __sumdigit(n):
    ret = 0
    while n > 0:
        ret += n % 10
        n //= 10
    return ret

def __zfunc(s):
    n = len(s)
    z = [0 for i in range(n)]
    l = 0
    r = 0
    for i in range(1, n):
        if r >= i:
            z[i] = min(z[i - l], r - i + 1)
        while z[i] + i < n and s[z[i]] == s[z[i] + i]:
            z[i] += 1
        if i + z[i] - 1 > r:
            l = i
            r = i + z[i] - 1
    return z

def __to(n, x):
    ret = ''
    while n > 0:
        q = n % x
        if q < 10:
            ret += str(q)
        else:
            ret += chr(q - 10 + ord('a'))
        n //= x
    return ret[::-1]

def solve(t):
    n = tinp()
    has = {}
    has[0] = True
    val = 1
    ans = {}
    for i in range(n):
        (c, x) = input().split()
        k = int(x)
        if c[0] == '+':
            has[k] = True
        else:
            w = k
            if w in ans:
                w = ans[w]
            while w in has:
                w += k
                ans[k] = w
            print(w)
t = 1
for i in range(t):
    solve(i + 1)