#G1117. [GESP202506 五级] 最大公因数

[GESP202506 五级] 最大公因数

[GESP202506 五级] 最大公因数

题目描述

对于两个正整数 a,ba, b,它们的最大公因数记为 gcd⁡(a,b)\gcd(a, b)。对于 k≥3k \ge 3 个正整数 c1,c2,…,ckc_1, c_2, \dots, c_k,它们的最大公因数为:

$$\gcd(c_1, c_2, \dots, c_k) = \gcd(\gcd(c_1, c_2, \dots, c_{k-1}), c_k)$$

给定 nn 个正整数 a1,a2,…,ana_1, a_2, \dots, a_n 以及 qq 组询问。对于第 ii(1≤i≤q1 \le i \le q)组询问,请求出 a1+i,a2+i,…,an+ia_1 + i, a_2 + i, \dots, a_n + i 的最大公因数,也即 gcd⁡(a1+i,a2+i,…,an+i)\gcd(a_1 + i, a_2 + i, \dots, a_n + i)。

输入格式

第一行,两个正整数 n,qn, q,分别表示给定正整数的数量,以及询问组数。

第二行,nn 个正整数 a1,a2,…,ana_1, a_2, \dots, a_n。

输出格式

输出共 qq 行,第 ii 行包含一个正整数,表示 a1+i,a2+i,…,an+ia_1 + i, a_2 + i, \dots, a_n + i 的最大公因数。

样例 #1

样例输入 #1

5 3
6 9 12 18 30

样例输出 #1

1
1
3

样例 #2

样例输入 #2

3 5
31 47 59

样例输出 #2

4
1
2
1
4

数据范围

测试点 nn qq aia_i
1~6(60%) ≤103\le 10^3 ≤10\le 10 ≤1000\le 1000
全部 ≤105\le 10^5