【模板】ST 表 && 区间最大公约数（GCD）问题

📘 题目背景

这是一道 ST 表的经典应用题，用来练习如何用 ST 表实现静态区间的 最大公约数（GCD） 查询。

🧾 题目描述

给定一个长度为 \(N\) 的整数数列，以及 \(M\) 次区间查询，每次查询给出一个闭区间 \([l_i, r_i]\)，请你输出该区间内所有数的 最大公约数（GCD）。

你需要使用 ST 表 数据结构，实现每次查询 \(O(1)\) 的算法。

🧩 输入格式

• 第一行包含两个整数 \(N, M\)，分别表示数列的长度和查询次数。
• 第二行包含 \(N\) 个整数 \(a_1, a_2, ..., a_N\)，表示数列的每一项。
• 接下来 \(M\) 行，每行包含两个整数 \(l_i, r_i\)，表示一次查询的左右端点（下标从 \(1\) 开始）。

📤 输出格式

• 共 \(M\) 行，每行一个整数，表示对应区间内所有元素的最大公约数。

📌 输入输出样例 #1

输入

8 5
12 18 6 9 15 21 27 30
1 3
2 5
4 6
1 8
3 3

输出

6
3
3
3
6

📊 数据范围与说明

• 对于 \(30%\) 的数据，\(1 \le N, M \le 10\)
• 对于 \(70%\) 的数据，\(1 \le N, M \le 10^5\)

• 对于 \(100%\) 的数据：

  • \(1 \le N \le 10^5\)
  • \(1 \le M \le 2 \times 10^6\)
  • \(1 \le a_i \le 10^9\)
  • \(1 \le l_i \le r_i \le N\)

🧠 提示

• GCD 运算是幂等函数，满足：gcd(a, a) = a

• ST 表支持对幂等性函数进行高效预处理和查询

• ST 表构建方式：

  st[i][0] = a[i]
  st[i][j] = gcd(st[i][j - 1], st[i + (1 << (j - 1))][j - 1])

• 查询区间 [l, r] 的结果为：

  k = log2(r - l + 1)
  result = gcd(st[l][k], st[r - (1 << k) + 1][k])