GESP 题解库 / 5 级题解 / [GESP202506 五级] 最大公因数 · 第 7 / 23 题
GESP202506 五级 · P13014 · 简单

最大公因数

q 组询问,第 i 组求 gcd(a₁+i, a₂+i, …, aₙ+i)。

📊
n, q ≤ 10⁵
数据规模
🔢
int / long long
数值类型
⚡
O(n log A + q log A)
时间复杂度
🎯
差值 gcd 不变式
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

给定 n 个正整数 a₁…aₙ 和 q 组询问。第 i 组询问求 gcd(a₁ + i, a₂ + i, …, aₙ + i)。

💡
人话翻译:每次询问是把所有数同时加上 i,再求它们的最大公因数。如果每次询问都重新算一遍,q 组就是 O(nq),太慢。关键洞察:所有数同时加一个数,"两两之差"保持不变——所以可以先预处理出所有差值的 gcd,之后每组询问只需一次 gcd 运算。

🔍 关键词提取

gcd 性质差值不变式预处理多次询问

已知条件

项目说明
输入第一行 n、q;第二行 n 个数;共 q 组询问(第 i 组就是 +i)
输出q 行,每行一个答案
数据范围n, q ≤ 10⁵
询问形式第 i 组询问为 a_j + i(j = 1…n)
核心性质同时加同一个数,差值不变

需要解决的问题

02
思维导图
整理解题思路的全貌
🔗 差值 gcd 不变式
🧠 核心性质
所有数同时加 i
两两之差完全不变
所以差的 gcd 也不变
记为 g
📐 化简结论
gcd(a₁+i, …, aₙ+i)
= gcd(a₁+i, a₂−a₁, …)
= gcd(a₁+i, g)
g = gcd of (a_j − a₁)
⚡ 加速查询
预处理一次 g:O(n log A)
每组询问 O(log A)
总共 O(n + q) 次 gcd
远快于 O(nq)
⚠️ 易错点
n = 1 时 g = 0,答案就是 a₁+i
差值要取绝对值
用 int 但答案可能大
忘记预处理导致超时
03
样例手算推导
两个样例的验证

🧮 样例 1:a = {6, 9, 12, 18, 30},询问 i = 1, 2, 3

先算差值 gcd。

1
预处理差值

以 a₁ = 6 为基准,其他数与它的差:

9 − 6 = 3、12 − 6 = 6、18 − 6 = 12、30 − 6 = 24

g = gcd(3, 6, 12, 24) = 3

g = 3

询问 ia₁ + igcd(a₁+i, g) = gcd(a₁+i, 3)答案
16 + 1 = 7gcd(7, 3)1
26 + 2 = 8gcd(8, 3)1
36 + 3 = 9gcd(9, 3)3

输出 1、1、3 ✓ 与样例一致

🔑
验证一下 i = 3 的情况:a 变成 {9, 12, 15, 21, 33},直接求 gcd(9,12,15,21,33)——都能被 3 整除,所以是 3 ✓。而 gcd(9, 3) = 3 一步就得到了,不用把 5 个数都算一遍。

🧮 样例 2:a = {31, 47, 59}

差值:47 − 31 = 16、59 − 31 = 28 → g = gcd(16, 28) = 4。

询问 ia₁ + igcd(a₁+i, 4)答案
132gcd(32, 4) = 44
233gcd(33, 4) = 11
334gcd(34, 4) = 22
435gcd(35, 4) = 11
536gcd(36, 4) = 44

输出 4、1、2、1、4 ✓ 与样例一致

💡
为什么这个等式成立?因为 gcd(x, y) = gcd(x, y − x)。反复使用:gcd(a₁+i, a₂+i) = gcd(a₁+i, a₂−a₁),再加上第三个数的运算,最终就得到 gcd(a₁+i, gcd(所有差值))。这是"更相减损术"的直接应用。
04
解法对比
预处理差值 gcd vs 每次重算

⚔️ 解法对比

🟢 预处理差值 gcd(推荐) 推荐

先算 g = gcd(所有 a_j − a_1),每组询问只需 gcd(a_1+i, g)

  • 预处理 O(n log A)
  • 每组询问 O(log A)
  • 总复杂度 O((n+q) log A)
  • 代码 15 行
💡
实现:int g = 0; for (j = 2; j <= n; j++) g = gcd(g, a[j] - a[1]); 然后每组询问输出 gcd(a[1] + i, g)。注意 gcd(x, 0) = x 这个性质让 n = 1 也能自然处理。

🟠 每组询问都重新求 gcd

对每个 i,遍历所有 n 个数求 gcd

  • 每组 O(n log A)
  • 总复杂度 O(nq log A)
  • n = q = 10⁵ 时约 10¹⁰ 次
  • 必然超时
⚠️
注意量级:n 和 q 都可达到 10⁵,相乘就是 10¹⁰,远超任何时间限制。必须利用"差值不变"这个性质把工作量降下来。

📈 性能对比

方案总复杂度n = q = 10⁵ 时
预处理差值O((n+q) log A)约 3 × 10⁶(可行)
每组重算O(nq log A)约 10¹⁰(超时)
05
算法流程图
预处理差值 gcd,再逐组回答
开始读入 n、q 和数组 ag = 0j 从 2 到 n:g = gcd(g, a[j] − a[1])i 从 1 到 q输出 gcd(a[1] + i, g)q 组询问都回答完了吗?结束i 加 1 继续
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🔗 多组询问最大公因数

第一行输入数组 a,第二行输入 q,程序会预留差值 gcd 并逐组给出答案。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码

#include <bits/stdc++.h>
using namespace std;

long long a[100005];

int main() {
    int n, q;
    scanf("%d %d", &n, &q);
    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);

    // 预处理:所有数与 a[1] 之差的 gcd
    long long g = 0;
    for (int j = 2; j <= n; j++) {
        g = __gcd(g, a[j] - a[1]);     // gcd(0, x) = x,所以初值取 0 天然正确
    }

    // 逐组回答
    for (long long i = 1; i <= q; i++) {
        printf("%lld\n", __gcd(a[1] + i, g));
    }
    return 0;
}
🔑
为什么 g 初值取 0 很方便?因为 gcd(0, x) = x,所以第一轮 g = gcd(0, a[2]-a[1]) = a[2]-a[1],相当于自动完成了初始化。而且 n = 1 时循环不执行,g 保持 0,此时答案 gcd(a[1]+i, 0) = a[1]+i 也正好正确——一个初值同时解决了两种情况。

📖 关键几行怎么看

代码作用为什么这样写
g = 0初值gcd(0, x) = x,天然处理首轮和 n = 1
g = gcd(g, a[j] - a[1])累积差值 gcd所有差值都是 g 的倍数
__gcd(a[1] + i, g)回答询问一步到位,不必遍历整个数组
long long类型a 的值和答案可能较大
⚠️
三个坑:① 每组询问都重新遍历求 gcd(O(nq) 超时);② g 初值取了 a[2]-a[1] 而不是 0,导致 n = 1 时出错;③ 用 int 但数值范围较大。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
5 3
6 9 12 18 30
1
1
3
题面样例 1
3 5
31 47 59
4
1
2
1
4
题面样例 2
1 3
7
8
9
10
n = 1 时 g = 0,答案就是 a₁ + i
2 2
5 5
6
7
两个数相同,差值 0,g = 0,答案即 a₁ + i
3 2
2 4 6
3
4
差值 2、4 → g = 2;gcd(3,2)=1…需按公式算
✅
自查清单:① 预处理了差值 gcd 吗?② g 初值取 0 吗?③ n = 1 的情况对吗?

🚨 易错点清单

⚠️
每组重算:O(nq) 会超时,必须预处理差值 gcd 后 O(1)(一次 gcd)回答。
⚠️
g 初值写错:应为 0(依赖 gcd(0,x)=x),否则 n = 1 时无法处理。
⚠️
差值没取绝对值:虽然 gcd 会自动处理符号,但为清晰起见可以主动取绝对值。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O((n + q) log A)
空间复杂度
O(n)
n, q 最大
10⁵
运算量
约 3 × 10⁶

时间怎么算的?

空间都用在哪?

需要存下数组 a(用于计算差值)。

✅ 约 300 万次运算,瞬间完成。相比 O(nq) 的 10¹⁰,优化了三个数量级。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 核心性质:gcd(a, b) = gcd(a, b - a)  (更相减损术)
// 推广:gcd(x + i, y + i) = gcd(x + i, y - x)
// 所以 gcd(a1+i, a2+i, ..., an+i) = gcd(a1+i, gcd(a2-a1, ..., an-a1))

// 求多个数的 gcd
long long g = 0;
for (int j = 2; j <= n; j++) g = __gcd(g, a[j] - a[1]);

// 单次询问
long long ans = __gcd(a[1] + i, g);

// 类似技巧:差分数组
// 把"同时加/减"的操作转化成"差值不变",是处理区间操作的常用手段

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
差值不变式同时加数 → 差值不变区间加减、平移类问题
gcd 更相减损gcd(x,y) = gcd(x,y−x)所有 gcd 相关的化简
预处理 + 快速查询把 O(n) 的判断降到 O(1)多次询问类题目
🌟
思考题:如果询问改成"第 i 组求 a₁ × i, a₂ × i, …, aₙ × i 的 gcd",还能用类似的技巧吗?(提示:gcd(a₁i, a₂i, …, aₙi) = i × gcd(a₁, …, aₙ),只需预处理一次所有数的 gcd,之后每组询问乘上 i 即可——同样是"预处理 + O(1) 查询"的思路。注意 i × g 可能较大,用 long long。)