CF1422F Boring Queries

Yura 拥有一个非常普通且无聊的长度为 $n$ 的数组 $a$。你认为没有什么比这更无聊的了，但 Vladik 并不这么认为！ 为了让 Yura 的数组变得更加无聊，Vladik 进行了 $q$ 次无聊的询问。每次询问包含两个整数 $x$ 和 $y$。在回答每个询问之前，需要计算本次询问的区间边界 $l$ 和 $r$：$l = (last + x) \bmod n + 1$，$r = (last + y) \bmod n + 1$，其中 $last$ 表示上一次询问的答案（初始为零），$\bmod$ 表示取余操作。如果 $l > r$，则交换 $l$ 和 $r$。 在 Vladik 计算出本次询问的 $l$ 和 $r$ 后，他需要计算初始数组 $a$ 的区间 $[l, r]$ 上所有元素的最小公倍数（LCM），并对 $10^9 + 7$ 取模。一个多重集合的 LCM 是能被集合中所有元素整除的最小正整数。所得的 LCM 即为本次询问的答案。 请帮助 Vladik 计算每次询问的答案！

第一行包含一个整数 $n$（$1 \le n \le 10^5$），表示数组的长度。 第二行包含 $n$ 个整数 $a_i$（$1 \le a_i \le 2 \times 10^5$），表示数组的元素。 第三行包含一个整数 $q$（$1 \le q \le 10^5$），表示询问的数量。 接下来的 $q$ 行，每行包含两个整数 $x$ 和 $y$（$1 \le x, y \le n$），表示每次询问的参数。

输出 $q$ 个整数，分别表示每次询问的答案。

考虑如下示例： - 第一次询问的区间边界为 $(0 + 1) \bmod 3 + 1 = 2$ 和 $(0 + 3) \bmod 3 + 1 = 1$。区间 $[1, 2]$ 的 LCM 为 $6$； - 第二次询问的区间边界为 $(6 + 3) \bmod 3 + 1 = 1$ 和 $(6 + 3) \bmod 3 + 1 = 1$。区间 $[1, 1]$ 的 LCM 为 $2$； - 第三次询问的区间边界为 $(2 + 2) \bmod 3 + 1 = 2$ 和 $(2 + 3) \bmod 3 + 1 = 3$。区间 $[2, 3]$ 的 LCM 为 $15$； - 第四次询问的区间边界为 $(15 + 2) \bmod 3 + 1 = 3$ 和 $(15 + 3) \bmod 3 + 1 = 1$。区间 $[1, 3]$ 的 LCM 为 $30$。 由 ChatGPT 4.1 翻译