最大公因数
时间限制:1 s,内存限制:512 MB
【问题描述】
对于两个正整数 a、b,它们的最大公因数记为 gcd(a, b)。对于 k >=3 个正整数 c1、c2、……、ck,它们的最大公因数为:
gcd(c1, c2, ……, ck) = gcd(gcd(c1, c2, ……, c(k-1), ck)
给定 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】
【样例输入2】
【样例输出2】
【数据范围】
对于60%的测试点,保证 1 <= n <= 1000,1 <= q <= 10。
对于所有测试点,保证 1 <= n、q <= 10^5,1 <= ai <= 1000。