← 返回题目

题库练习 [GESP202506 五级] 最大公因数

← 上一题下一题 →

A5105 | $[GESP202506 五级] 最大公因数$

来源2025

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

对于两个正整数 $a,b$，他们的最大公因数记为 $\gcd(a,b)$。对于 $k > 3$ 个正整数 $c_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)$$ 给定 $n$ 个正整数 $a_1,a_2,\dots,a_n$ 以及 $q$ 组询问。对于第 $i(1 \le i \le q)$ 组询问，请求出 $a_1+i,a_2+i,\dots,a_n+i$ 的最大公因数，也即 $\gcd(a_1+i,a_2+i,\dots,a_n+i)$。

输入格式

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

输出格式

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

输入输出样例

输入 #1

5 3
6 9 12 18 30

输出 #1

1
1
3

输入 #2

3 5
31 47 59

输出 #2

C++ 编辑器

输入

输出