[GESP202506 五级] 最大公因数
题目描述
对于两个正整数 a,b,它们的最大公因数记为 gcd(a,b)。对于 k≥3 个正整数 c1,c2,…,ck,它们的最大公因数为:
$$\gcd(c_1, c_2, \dots, c_k) = \gcd(\gcd(c_1, c_2, \dots, c_{k-1}), c_k)$$
给定 n 个正整数 a1,a2,…,an 以及 q 组询问。对于第 i(1≤i≤q)组询问,请求出 a1+i,a2+i,…,an+i 的最大公因数,也即 gcd(a1+i,a2+i,…,an+i)。
输入格式
第一行,两个正整数 n,q,分别表示给定正整数的数量,以及询问组数。
第二行,n 个正整数 a1,a2,…,an。
输出格式
输出共 q 行,第 i 行包含一个正整数,表示 a1+i,a2+i,…,an+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
数据范围
| 测试点 |
n |
q |
ai |
| 1~6(60%) |
≤103 |
≤10 |
≤1000 |
| 全部 |
≤105 |