Bash and a Tough Math Puzzle (Codeforces 914D)
Tags: Others, number theory

Bash likes playing with arrays. He has an array a1, a2, ... an of n integers. He likes to guess the greatest common divisor (gcd) of different segments of the array. Of course, sometimes the guess is not correct. However, Bash will be satisfied if his guess is almost correct.Suppose he guesses that the gcd of the elements in the range [l, r] of a is x. He considers the guess to be almost correct if he can change at most one element in the segment such that the gcd of the segment is x after making the change. Note that when he guesses, he doesn't actually change the array — he just wonders if the gcd of the segment can be made x. Apart from this, he also sometimes makes changes to the array itself.Since he can't figure it out himself, Bash wants you to tell him which of his guesses are almost correct. Formally, you have to process q queries of one of the following forms:  1 l r x — Bash guesses that the gcd of the range [l, r] is x. Report if this guess is almost correct.  2 i y — Bash sets ai to y. Note: The array is 1-indexed.

Input: The first line contains an integer n (1 ≤ n ≤ 5·105)  — the size of the array.The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 109)  — the elements of the array.The third line contains an integer q (1 ≤ q ≤ 4·105)  — the number of queries.The next q lines describe the queries and may have one of the following forms:  1 l r x (1 ≤ l ≤ r ≤ n, 1 ≤ x ≤ 109).  2 i y (1 ≤ i ≤ n, 1 ≤ y ≤ 109). Guaranteed, that there is at least one query of first type.

Output: For each query of first type, output "YES" (without quotes) if Bash's guess is almost correct and "NO" (without quotes) otherwise.

Note: In the first sample, the array initially is {2, 6, 3}. For query 1, the first two numbers already have their gcd as 2.For query 2, we can achieve a gcd of 3 by changing the first element of the array to 3. Note that the changes made during queries of type 1 are temporary and do not get reflected in the array. After query 3, the array is now {9, 6, 3}. For query 4, no matter which element you change, you cannot get the gcd of the range to be 2. 

Sample Inputs:
3
2 6 3
4
1 1 2 2
1 1 3 3
2 1 9
1 1 3 2

5
1 2 3 4 5
6
1 1 4 2
2 3 6
1 1 4 2
1 1 5 2
2 5 10
1 1 5 2

Sample Outputs:
YES
YES
NO

NO
YES
NO
YES

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

def update(i, x):
    i += l1
    tree[i] = x
    i //= 2
    while i:
        tree[i] = math.gcd(tree[2 * i], tree[2 * i + 1])
        i //= 2
    return

def f(l, r, x):
    (s, t) = (l + l1, r + l1)
    u = s
    while s <= t:
        if s % 2 == 0:
            s //= 2
        else:
            if tree[s] % x:
                u = s
            s = (s + 1) // 2
        if t % 2 == 1:
            t //= 2
        else:
            if tree[t] % x:
                u = t
            t = (t - 1) // 2
    while u < l1:
        u = 2 * u if tree[2 * u] % x else 2 * u + 1
    return u - l1

def ok(l, r, x):
    (s, t) = (l + l1, r + l1)
    while s <= t:
        if s % 2 == 0:
            s //= 2
        else:
            if tree[s] % x:
                return False
            s = (s + 1) // 2
        if t % 2 == 1:
            t //= 2
        else:
            if tree[t] % x:
                return False
            t = (t - 1) // 2
    return True
n = int(input())
a = [0] + list(map(int, input().split()))
l1 = pow(2, (n + 2).bit_length())
l2 = 2 * l1
tree = [0] * l2
for i in range(n + 1):
    tree[i + l1] = a[i]
for i in range(l1 - 1, 0, -1):
    tree[i] = math.gcd(tree[2 * i], tree[2 * i + 1])
q = int(input())
ans = []
for _ in range(q):
    t = list(map(int, input().split()))
    if t[0] == 1:
        (l, r, x) = t[1:]
        if l == r or ok(l, r, x):
            ans0 = 'YES'
        else:
            m = f(l, r, x)
            ans0 = 'YES' if ok(l, m - 1, x) and ok(m + 1, r, x) else 'NO'
        ans.append(ans0)
    else:
        (i, y) = t[1:]
        a[i] = y
        update(i, y)
sys.stdout.write('\n'.join(map(str, ans)))

Solution (Python):
import os
import sys
from atexit import register
from io import StringIO
from math import gcd
sys.stdin = StringIO(os.read(0, os.fstat(0).st_size).decode())
sys.stdout = StringIO()
register(lambda : os.write(1, sys.stdout.getvalue().encode()))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def main():
    n = int(input())
    arr = [int(num) for num in input().split()]
    a = [0] * (524288 << 1 | 1)
    for i in range(n):
        p = i + 524289
        a[p] = arr[i]
        while p != 1:
            p >>= 1
            a[p] = gcd(a[p << 1], a[p << 1 | 1])
    q = int(input())
    for _ in range(q):
        query = [int(num) for num in input().split()]
        if query[0] == 1:
            p = 524288 + query[1]
            while p != 1 and a[p] % query[3] == 0:
                if p & p + 1 == 0:
                    p = n + 524289
                    break
                p = p + 1 >> 1
            while p < 524288:
                p <<= 1
                p += int(a[p] % query[3] == 0)
            if p - 524288 >= query[2]:
                print('YES')
            else:
                p += 1
                while p != 1 and a[p] % query[3] == 0:
                    if p & p + 1 == 0:
                        p = n + 524289
                        break
                    p = p + 1 >> 1
                while p < 524288:
                    p <<= 1
                    p += int(a[p] % query[3] == 0)
                print('YES' if p - 524288 > query[2] else 'NO')
        else:
            p = query[1] + 524288
            a[p] = query[2]
            while p != 1:
                p >>= 1
                a[p] = gcd(a[p << 1], a[p << 1 | 1])
if __name__ == '__main__':
    main()

Solution (Python):
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import inf, log2

class SegmentTree:

    def __init__(self, array, func=max):
        self.n = len(array)
        self.size = 2 ** (int(log2(self.n - 1)) + 1) if self.n != 1 else 1
        self.func = func
        self.default = 0 if self.func != min else inf
        self.data = [self.default] * (2 * self.size)
        self.process(array)

    def process(self, array):
        self.data[self.size:self.size + self.n] = array
        for i in range(self.size - 1, -1, -1):
            self.data[i] = self.func(self.data[2 * i], self.data[2 * i + 1])

    def query(self, alpha, omega):
        """"""
        if alpha == omega:
            return self.data[alpha + self.size]
        res = self.default
        alpha += self.size
        omega += self.size + 1
        while alpha < omega:
            if alpha & 1:
                res = self.func(res, self.data[alpha])
                alpha += 1
            if omega & 1:
                omega -= 1
                res = self.func(res, self.data[omega])
            alpha >>= 1
            omega >>= 1
        return res

    def update(self, index, value):
        """"""
        index += self.size
        self.data[index] = value
        index >>= 1
        while index:
            self.data[index] = self.func(self.data[2 * index], self.data[2 * index + 1])
            index >>= 1
from math import gcd
n = int(input())
a = list(map(int, input().split()))
st = SegmentTree(a, func=gcd)

def check(n, alpha, omega, x):
    while alpha < omega:
        mid = (alpha + omega) // 2
        left = st.query(alpha, mid)
        right = st.query(mid + 1, omega)
        if left % x and right % x:
            return False
        if not left % x and (not right % x):
            return True
        if not left % x and n == 500000 or left % x != 0:
            omega = mid
        else:
            alpha = mid + 1
    return True
for _ in range(int(input())):
    s = map(int, input().split())
    s = list(s)
    if len(s) == 4:
        (p, l, r, x) = s
        print('YES' if check(n, l - 1, r - 1, x) else 'NO')
    else:
        (p, i, y) = s
        st.update(i - 1, y)