[GESP202506 五级] 最大公因数

✏️ 纠错

第 133 题 / 共 155 题

题目描述

对于两个正整数 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，分别表示给定正整数的数量，以及询问组数。

第二行，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

说明/提示

对于 60% 的测试点，保证 1≤n≤103，1≤q≤10。

对于所有测试点，保证 1≤n≤105，1≤q≤105，1≤ai≤1000。

🎉

回答正确！

你真棒！

📝 题目解析

【解析】

1.核心问题：对于每个i，计算gcd(a₁+i,a₂+i,...,a_n+i)。

2.关键观察：

设d是所求公因数，则d必能整除任意两数的差：(a_j+i) - (a_k+i) = a_jj-a_k。

因此，d是所有a_j-a_k的公因数，即d整除这些差的最大公因数g。

3.算法步骤：

计算所有a_i差值的最大公因数g（通过排序后计算相邻差的gcd）。

对第i组询问，答案为gcd(g,a₁+i（因g已包含所有差值信息）。

参考程序

#include <cstdio>
#include <algorithm>
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() {
    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++)
        g = gcd(g, a[i] - a[i - 1]);
    for (int i = 1; i <= q; i++)
        printf("%d\n", gcd(g, a[1] + i));
    return 0;
}