A26836. 最大公因数
填空题
困难
知识点
题目描述
最大公因数
题目描述
对于两个正整数 a,b，它们的最大公因数记为 gcd(a,b)。对于k≥3个正整数 c1,c2,……,ck，它们的最大公因数为: gcd(c1,c2,……,ck) = gcd(gcd(c1,c2,……,ck-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，分别表示给定正整数的数量，以及询问组数。
第二行，几个正整数 a1,a2,……,an。
输出格式
输出共q行，第i行包含一个正整数，表示 a1 +i,a2+i,……,an +i 的最大公因数。
样例
输入样例 1
5 3
6 9 12 18 30输出样例 1
1
1
3输入样例 2
3 5
31 47 59输出样例 2
4
1
2
1
4数据范围
对于 60% 的测试点，保证1≤n≤ 103，1≤q≤ 10。
对于所有测试点，保证1≤n≤105,1≤q≤105，1≤ai≤ 1000。
参考答案
# 得到n和q
n, q = map(int, input().split())
# 对n个数进行排序
a = sorted(list(map(int, input().split())))
# 欧几里得算法求a和b的最大公约数
def gcd(a, b):
if a == 0 or b == 0:
return a + b
return gcd(b, a % b)
g = 0
for i in range(1, n):
g = gcd(g, a[i] - a[i - 1])
for i in range(q):
print(gcd(g, a[0] + i + 1))
上一题
下一题