GCD of an Array (Codeforces 1493D)
Tags: Math, hashing

You are given an array $$$a$$$ of length $$$n$$$. You are asked to process $$$q$$$ queries of the following format: given integers $$$i$$$ and $$$x$$$, multiply $$$a_i$$$ by $$$x$$$.After processing each query you need to output the greatest common divisor (GCD) of all elements of the array $$$a$$$.Since the answer can be too large, you are asked to output it modulo $$$10^9+7$$$.

Input: The first line contains two integers — $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10^5$$$).The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 2 \cdot 10^5$$$) — the elements of the array $$$a$$$ before the changes.The next $$$q$$$ lines contain queries in the following format: each line contains two integers $$$i$$$ and $$$x$$$ ($$$1 \le i \le n$$$, $$$1 \le x \le 2 \cdot 10^5$$$).

Output: Print $$$q$$$ lines: after processing each query output the GCD of all elements modulo $$$10^9+7$$$ on a separate line.

Note: After the first query the array is $$$[12, 6, 8, 12]$$$, $$$\operatorname{gcd}(12, 6, 8, 12) = 2$$$.After the second query — $$$[12, 18, 8, 12]$$$, $$$\operatorname{gcd}(12, 18, 8, 12) = 2$$$.After the third query — $$$[12, 18, 24, 12]$$$, $$$\operatorname{gcd}(12, 18, 24, 12) = 6$$$.Here the $$$\operatorname{gcd}$$$ function denotes the greatest common divisor.

Sample Inputs:
4 3
1 6 8 12
1 12
2 3
3 3

Sample Outputs:
2
2
6

Solution (Python):
from sys import stdin, stdout
import collections, heapq, bisect, math
input = stdin.readline

def rint():
    return int(input())

def rstr():
    return input().strip()

def rlstr():
    return list(input().strip().split())

def rlint():
    return list(map(int, input().split()))

def seive():
    n = 2 * 10 ** 5
    prime = [0] * (n + 1)
    for i in range(2, n + 1):
        if prime[i] == 0:
            prime[i] = i
            for j in range(i * i, n + 1, i):
                if prime[j] == 0:
                    prime[j] = i
    return prime
prime = seive()
res = 1
mod = 10 ** 9 + 7

def add(i, x, n):
    global res
    while x != 1:
        v = prime[x]
        f = 0
        while v == prime[x]:
            x //= v
            f += 1
        prev = 0
        if v in pf[i]:
            prev = pf[i][v]
            pf[i][v] += f
        else:
            pf[i][v] = f
        for c in range(prev + 1, prev + f + 1):
            if len(count[v]) < c:
                count[v].append(1)
            else:
                count[v][c - 1] += 1
            if count[v][c - 1] == n:
                res = res * v % mod

def main():
    (n, q) = rlint()
    global pf, count
    pf = [{} for _ in range(n)]
    count = collections.defaultdict(list)
    arr = rlint()
    for i in range(n):
        add(i, arr[i], n)
    for _ in range(q):
        (i, x) = rlint()
        add(i - 1, x, n)
        print(res)
if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
mod = 10 ** 9 + 7
import math

def sieve(n):
    prime = [-1] * (n + 1)
    for i in range(2, n + 1):
        if prime[i] == -1:
            prime[i] = i
            for j in range(i * i, n + 1, i):
                if prime[j] == -1:
                    prime[j] = i
    return prime

def find_pf(ind, num):
    global hcf
    while num != 1:
        v = values[num]
        c = 0
        while values[num] == v:
            num = num // v
            c += 1
        prev = 0
        if v in pf[ind]:
            prev = pf[ind][v]
            pf[ind][v] += c
        else:
            pf[ind][v] = c
        for i in range(prev + 1, prev + c + 1):
            if v in count:
                if len(count[v]) < i:
                    count[v].append(1)
                else:
                    count[v][i - 1] += 1
            else:
                count[v] = [1]
            if count[v][i - 1] == n:
                hcf = hcf * v % mod
values = sieve(300000)
(n, q) = map(int, input().split())
a = list(map(int, input().split()))
hcf = 1
pf = [{} for i in range(n)]
count = {}
for i in range(n):
    find_pf(i, a[i])
for i in range(q):
    (i, x) = map(int, input().split())
    find_pf(i - 1, x)
    print(hcf)

Solution (Python):
import sys
from sys import stdin
import math
mod = 10 ** 9 + 7

def inverse(a, mod):
    return pow(a, mod - 2, mod)

def Sieve(n):
    ret = []
    divlis = [-1] * (n + 1)
    flag = [True] * (n + 1)
    flag[0] = False
    flag[1] = False
    ind = 2
    while ind <= n:
        if flag[ind]:
            ret.append(ind)
            ind2 = ind ** 2
            while ind2 <= n:
                flag[ind2] = False
                divlis[ind2] = ind
                ind2 += ind
        ind += 1
    return (ret, divlis)
(tmp, divlis) = Sieve(200001)
(n, q) = map(int, stdin.readline().split())
a = list(map(int, stdin.readline().split()))
d = [{} for i in range(n)]
for i in range(n):
    na = a[i]
    while divlis[na] != -1:
        if divlis[na] not in d[i]:
            d[i][divlis[na]] = 1
        else:
            d[i][divlis[na]] += 1
        na //= divlis[na]
    if na != 1:
        if na not in d[i]:
            d[i][na] = 1
        else:
            d[i][na] += 1
ix = []
for loop in range(q):
    (i, x) = map(int, stdin.readline().split())
    i -= 1
    ix.append((i, x))
    na = x
    while divlis[na] != -1:
        if divlis[na] not in d[i]:
            d[i][divlis[na]] = 1
        else:
            d[i][divlis[na]] += 1
        na //= divlis[na]
    if na != 1:
        if na not in d[i]:
            d[i][na] = 1
        else:
            d[i][na] += 1
ans = {}
for v in d[0]:
    ans[v] = d[0][v]
for i in range(1, n):
    nex = d[i]
    dlis = []
    for v in ans:
        if v not in nex:
            dlis.append(v)
        else:
            ans[v] = min(ans[v], nex[v])
    for v in dlis:
        del ans[v]
ANSLIS = []
PANS = 1
for v in ans:
    PANS = PANS * pow(v, ans[v], mod) % mod
ix.reverse()
for (i, x) in ix:
    ANSLIS.append(PANS)
    na = x
    touch = set([])
    while divlis[na] != -1:
        d[i][divlis[na]] -= 1
        touch.add(divlis[na])
        na //= divlis[na]
    if na != 1:
        touch.add(na)
        d[i][na] -= 1
    for v in touch:
        if v in ans and ans[v] > d[i][v]:
            PANS = PANS * inverse(pow(v, ans[v] - d[i][v], mod), mod) % mod
            ans[v] = d[i][v]
ANSLIS.reverse()
print('\n'.join(map(str, ANSLIS)))