【算法实战】每日一题：18.3 ST表 - 给定一个整数序列和一系列区间查询，求每个查询区间内所有整数的最大公约数。

题目

给定一个整数序列和一系列区间查询，求每个查询区间内所有整数的最大公约数。

思路

上一节我们详细的学完ST表后，这里就比较好算了，直接把ST表的板子换一下增加一个GCD即可

解决方案

import math

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

def build_gcd_arr(arr):
    n = len(arr)
    k = int(math.log2(n)) + 1
    gcd_arr = [[0] * k for _ in range(n)]

    for i in range(n):
        gcd_arr[i][0] = arr[i]

    j = 1
    while (1 << j) <= n:
        i = 0
        while i + (1 << j) - 1 < n:
            gcd_arr[i][j] = gcd(gcd_arr[i][j-1], gcd_arr[i + (1 << (j-1))][j-1])
            i += 1
        j += 1

    return gcd_arr

def query_gcd(gcd_arr, l, r):
    k = int(math.log2(r - l + 1))
    return gcd(gcd_arr[l][k], gcd_arr[r - (1 << k) + 1][k])

def main():
    n, m = map(int, input().split()) 
    arr = list(map(int, input().split()))

    gcd_arr = build_gcd_arr(arr)

    for _ in range(m):
        l, r = map(int, input().split())
        print(query_gcd(gcd_arr, l-1, r-1))

if __name__ == "__main__":
    main()

END