Mahmoud and Ehab and another array construction task (Codeforces 959D)
Tags: Math, number theory

Mahmoud has an array a consisting of n integers. He asked Ehab to find another array b of the same length such that:  b is lexicographically greater than or equal to a.  bi ≥ 2.  b is pairwise coprime: for every 1 ≤ i < j ≤ n, bi and bj are coprime, i. e. GCD(bi, bj) = 1, where GCD(w, z) is the greatest common divisor of w and z. Ehab wants to choose a special array so he wants the lexicographically minimal array between all the variants. Can you find it?An array x is lexicographically greater than an array y if there exists an index i such than xi > yi and xj = yj for all 1 ≤ j < i. An array x is equal to an array y if xi = yi for all 1 ≤ i ≤ n.

Input: The first line contains an integer n (1 ≤ n ≤ 105), the number of elements in a and b.The second line contains n integers a1, a2, ..., an (2 ≤ ai ≤ 105), the elements of a.

Output: Output n space-separated integers, the i-th of them representing bi.

Note: Note that in the second sample, the array is already pairwise coprime so we printed it.

Sample Inputs:
5
2 3 5 4 13

3
10 3 7

Sample Outputs:
2 3 5 7 11

10 3 7

Solution (Python):
def get_primes(n):
    sieve = [True] * n
    p = []
    for i in range(2, n):
        if sieve[i]:
            p.append(i)
            for j in range(i * i, n, i):
                sieve[j] = False
    return p

def prime_factors(a, p):
    f = []
    for x in p:
        if x * x > a:
            break
        if a % x == 0:
            f.append(x)
            while a % x == 0:
                a //= x
    if a > 1:
        f.append(a)
    return f
p = get_primes(1310000)
n = int(input())
factors = set()
b = []
for (i, x) in enumerate(map(int, input().split())):
    f = prime_factors(x, p)
    if factors.isdisjoint(f):
        b.append(x)
        factors.update(f)
        continue
    x += 1
    while not factors.isdisjoint((f := prime_factors(x, p))):
        x += 1
    b.append(x)
    factors.update(f)
    for f in factors:
        p.remove(f)
    b += p[:n - len(b)]
    break
print(' '.join((str(x) for x in b)))

Solution (Python):
import bisect

def get_primes(n):
    sieve = [True] * n
    p = []
    for i in range(2, n):
        if sieve[i]:
            p.append(i)
            for j in range(i * i, n, i):
                sieve[j] = False
    return p

def prime_factors(a, p):
    a0 = a
    f = []
    for x in p:
        if a == 1:
            return f
        if x * x > a:
            f.append(a)
            return f
        if a % x == 0:
            f.append(x)
            while a % x == 0:
                a //= x
    assert False
p = get_primes(1310000)
p0 = p[:67]
n = int(input())
a = list(map(int, input().split()))
f = set()
b = []
for i in range(n):
    g = prime_factors(a[i], p0)
    if not f.isdisjoint(g):
        u = a[i] + 1
        while True:
            g = prime_factors(u, p0)
            if not f.isdisjoint(g):
                u += 1
                continue
            f.update(g)
            b.append(u)
            break
        break
    b.append(a[i])
    f.update(g)
else:
    i = n
if i < n:
    for x in f:
        p.remove(x)
    assert len(b) + len(p) >= n
    b += p[:n - i - 1]
print(' '.join((str(x) for x in b)))

Solution (Python):
import atexit
import io
import sys
_INPUT_LINES = sys.stdin.read().splitlines()
input = iter(_INPUT_LINES).__next__
_OUTPUT_BUFFER = io.StringIO()
sys.stdout = _OUTPUT_BUFFER

@atexit.register
def write():
    sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())
ppp = '2      3      5      7     11     13     17     19     23     29 ' + '31     37     41     43     47     53     59     61     67     71 ' + '73     79     83     89     97    101    103    107    109    113 ' + '127    131    137    139    149    151    157    163    167    173 ' + '179    181    191    193    197    199    211    223    227    229 ' + '233    239    241    251    257    263    269    271    277    281 ' + '283    293    307    311    313    317 '
pp = [int(x) for x in ppp.split()]
xx = [False] * 1500000

def f(aa):
    t = []
    for p in pp:
        if aa % p == 0:
            while aa % p == 0:
                aa = aa // p
            t.append(p)
            if aa == 1:
                break
    if aa != 1:
        t.append(aa)
    for tt in t:
        for i in range(tt, 1500000, tt):
            xx[i] = True

def main():
    n = input()
    a = [int(x) for x in input().split()]
    b = []
    for aa in a:
        if xx[aa] == False:
            b.append(aa)
            f(aa)
        else:
            kk = aa + 1
            while xx[kk] == True:
                kk += 1
            b.append(kk)
            f(kk)
            break
    t = 2
    while len(b) < len(a):
        while xx[t] == True:
            t += 1
        b.append(t)
        f(t)
    print(' '.join((str(x) for x in b)))
if __name__ == '__main__':
    main()