[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$。

提交链接

https://www.luogu.com.cn/problem/P13014

思路分析

🔍 暴力解法，适用于 $60\%$ 数据

我们观察题目的形式，会发现每次查询是对整个数组加上一个偏移量 $i$，然后再计算它们的最大公因数。这种问题在数据范围较小时，可以直接暴力解决。

1. 暴力模拟每个询问

• 对于每次询问 $i$，我们把数组中每个元素都加上 $i$，得到一个新的数组。

• 然后，我们对新数组依次计算 gcd。

• 由于 gcd 满足结合律，我们可以通过从前往后扫描数组，依次更新当前的 gcd 值。

例如，若有数组：

a = [6, 9, 12]
i = 1
则变为 [7, 10, 13]
然后计算 gcd(7, 10, 13)

实现方式：

• 初始设 $gcd=a[0]+i$
• 然后遍历其余元素：$gcd=\gcd (gcd,a[j]+i)$

最终的 $gcd$ 就是这一组询问的答案。

2. 算法复杂度分析

• 外层：询问数量为 $q$
• 内层：每次询问需要遍历 $n$ 个元素
• 总体复杂度为 $O(q\cdot n)$

对于题目中说的 $60\%$ 数据范围（$n\le 1000,q\le 10$），这个复杂度是可以接受的：$1000\times 10=10^4$ 次 $gcd$ 计算。

---

参考代码

#include <bits/stdc++.h>
using namespace std;int main()
{int n, q;cin >> n >> q;   //n个数字  q次询问vector<int> a(n);for (int &i : a)cin >> i;for(int i = 1; i <= q; i++)  //q次询问{int gcd = a[0] + i;for(int j = 1; j < n; j++)gcd = __gcd(gcd , a[j] + i);cout << gcd << endl;}return 0;
}

✅ 解题思路（优化做法，适用于 $100\%$ 数据）

🔍 问题本质转化

我们要计算每次查询：gcd(a₁ + i, a₂ + i, ..., aₙ + i)

$q$ 次对 $n$ 个数求 GCD，暴力做法时间复杂度是 $O(q\cdot n)$，显然会超时。但我们可以利用 GCD 的平移不变性 和 结合律 优化这个过程。

🧠 核心数学性质

一个关键性质是：

• gcd(x + a₁, x + a₂, ..., x + aₙ) = gcd(x + a₁, a₂ - a₁, a₃ - a₁, ..., aₙ - a₁)

也就是说，我们可以把所有的 $a_i+x$ 表达成：gcd(a₁ + x, d₂, d₃, ..., dₙ)

其中 $d_i=a_i-a_1$，即所有数与第一个数的差。

💡 为什么这个公式成立？

这个公式的核心原理来源于 GCD 的不变性 和 GCD 对加减法的封闭性：

对于任意整数 $u,v$，都有：gcd(u, v) = gcd(u, v - u)

这是我们在辗转相除法（欧几里得算法）中使用的基本规则。

🧠 用在这个问题里，我们怎么理解？

我们要求的是：g = gcd(x + a₁, x + a₂, ..., x + aₙ)

我们可以把所有的数都减去 $(x+a_1)$，即：

(x + a₂) - (x + a₁) = a₂ - a₁  
(x + a₃) - (x + a₁) = a₃ - a₁  
...  
(x + aₙ) - (x + a₁) = aₙ - a₁

根据 $gcd$ 的性质，这种减法不会改变最终的 $gcd$ 结果。所以我们可以把上面的式子变形为：

• gcd(x + a₁, a₂ - a₁, a₃ - a₁, ..., aₙ - a₁)

✅ 举个例子理解

假设：a = [6, 9, 12]

查询值：x = 1

我们要求：gcd(6 + 1, 9 + 1, 12 + 1) = gcd(7, 10, 13)

现在按照公式转换：

x + a₁ = 7  
差值：  
9 - 6 = 3  
12 - 6 = 6

转化为：gcd(7, 3, 6)

继续计算：

gcd(7, 3) = 1  
gcd(1, 6) = 1

结果是：$1$，与原始计算：gcd(7, 10, 13) 得到的结果一致。

⚙️ 实现方式

我们可以将这些差值的 GCD 预处理出来，代码如下：

int g = a[1] - a[0];
for (int i = 2; i < n; i++) {g = __gcd(g, abs(a[i] - a[0]));
}

然后每次查询只需要计算：

__gcd(a[0] + x, g);

这就将 $O(q\cdot n)$ 优化成了 $O(n+q\log A)$。

🔧 代码分析

差值 gcd 预处理

int g = a[1] - a[0];
for(int i = 2; i < n; i++) 
{g = __gcd(g , abs(a[i] - a[0]));
}

这段代码做的是：将所有差值的 $gcd$ 预处理出来，时间复杂度 $O(n)$。

查询处理：

for(int i = 1; i <= q; i++) {int gcd = __gcd(g , a[0] + i);cout << gcd << endl;
}

每次查询的时间复杂度是 $O(\log A)$。

📌 时间复杂度分析

• 差值 $gcd$ 预处理：$O(n)$
• 每次查询：$O(\log A)$，总共 $q$ 次，复杂度为 $O(q\log A)$
• 总体时间复杂度：$O(n+q\log A)$

这个复杂度对于题目给定的最大范围 $n,q\le 10^5$ 是完全可以接受的。

参考代码

#include <bits/stdc++.h>
using namespace std;int main()
{int n, q;cin >> n >> q; // n个数字  q次询问vector<int> a(n);for (int &i : a)cin >> i;int g = 0;for (auto it : a)g = __gcd(g, abs(it - a[0]));for (int i = 1; i <= q; i++) // q次询问{int gcd = __gcd(g, a[0] + i);cout << gcd << endl;}return 0;
}