简答题 偏难
#20268

最大公因数 时间限制:1 s,内存限制:512 MB 【问题描述】 对于两个正整数 a、b,它们的最大公因数记为 gcd(a, b)。对于 k >=3 个正整数…

最大公因数

时间限制: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】

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 <= 1000,1 <= q <= 10。

对于所有测试点,保证 1 <= n、q <= 10^5,1 <= ai <= 1000。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;iostream&gt; #include &lt;algorithm&gt; using namespace std; const int N = 1e5 + 5; int n, q, a[N], g; int gcd(int a, int b) {     if (a == 0 || b == 0)         return a + b;     return gcd(b, a % b); } int main() {     cin &gt;&gt; n &gt;&gt; q;     for (int i = 1; i &lt;= n; i++)         cin &gt;&gt; a[i];     sort(a + 1, a + n + 1);     for (int i = 2; i &lt;= n; i++)         g = gcd(g, a[i] - a[i - 1]);     for (int i = 1; i &lt;= q; i++)         cout &lt;&lt; gcd(g, a[1] + i) &lt;&lt; endl;     return 0; }</pre>
这道题暂未补解析。