← 返回题目

题库练习最大公因数

← 上一题下一题 →

A71908 | $最大公因数$

来源编程题

时间限制1s

内存限制512MB

通过 / 提交0/0

题目描述

对于两个正整数 a，b，它们的最大公因数记为 gcd(a，b)。对于 k \ge 3 个正整数 c_1，c_2，...，c_k ，它们的最大公因数为： gcd(c_1，c_2，...，c_k)=gcd(gcd(c_1，c_2，...，c_{k-1}),c_k) 给定 n 个正整数 a_1，a_2，...，a_n 以及 q 组询问。对于第 i(1 \le i \le q)组询问，请求出 a_1+i，a_2+i，...，a_n+i 的最大公因数，也即 gcd(a_1+i，a_2+i，...，a_n+i)。

输入格式

第一行，两个正整数 n，q ，分别表示给定正整数的数量，以及询问组数。 第二行， n 个正整数 a_1，a_2，...，a_n 。

输出格式

输出共 q 行，第 i 行包含一个正整数，表示 a_1+i，a_2+i，...，a_n+i 的最大公因数。

输入输出样例

输入 #1

5 3
6 9 12 18 30

输出 #1

1
1
3

输入 #2

3 5
31 47 59

输出 #2

C++ 编辑器

输入

输出