P13014 [GESP202506 五级] 最大公因数

题目描述

对于两个正整数 $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

输入 #1

5 3
6 9 12 18 30

输出 #1

1
1
3

输入输出样例 #2

输入 #2

3 5
31 47 59

输出 #2

4
1
2
1
4

说明/提示

对于 $60\%$ 的测试点，保证 $1\le n\le 10^3$，$1\le q\le 10$。

对于所有测试点，保证 $1\le n\le 10^5$，$1\le q\le 10^5$，$1\le a_i\le 1000$。

一个悲伤的故事

本人是一个毫无实力的OIder，上个月考GESP5级的时候，我竟然还没有知道_gcd()和_lcm()这两个真神函数，结果考试的时候自己写的函数爆炸了，成功的与AK擦肩而过了（悲伤啊）

最爱的代码时间到

#include <bits/stdc++.h>
using namespace std;
int n, q, a[100005], d;
int main()
{
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++){
        scanf("%d", &a[i]);
    }
    sort(a + 1, a + n + 1);
    for (int i = 2; i <= n; i++){
        d = __gcd(d, a[i] - a[i - 1]);
    }
    for (int i = 1; i <= q; i++){
        printf("%d\n", __gcd(d, a[1] + i));
    }
    return 0;
}

喜欢博主记得点个赞欧！