q 组询问,第 i 组求 gcd(a₁+i, a₂+i, …, aₙ+i)。
给定 n 个正整数 a₁…aₙ 和 q 组询问。第 i 组询问求 gcd(a₁ + i, a₂ + i, …, aₙ + i)。
gcd 性质差值不变式预处理多次询问
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 n、q;第二行 n 个数;共 q 组询问(第 i 组就是 +i) |
| 输出 | q 行,每行一个答案 |
| 数据范围 | n, q ≤ 10⁵ |
| 询问形式 | 第 i 组询问为 a_j + i(j = 1…n) |
| 核心性质 | 同时加同一个数,差值不变 |
g = gcd(a₂ − a₁, a₃ − a₁, …, aₙ − a₁),那么所有 a_j + i 两两之差都是 g 的倍数gcd(a₁+i, a₂+i, …, aₙ+i) = gcd(a₁ + i, g)g = 0,所以答案是 gcd(a₁ + i, 0) = a₁ + i先算差值 gcd。
以 a₁ = 6 为基准,其他数与它的差:
9 − 6 = 3、12 − 6 = 6、18 − 6 = 12、30 − 6 = 24
g = gcd(3, 6, 12, 24) = 3
g = 3
| 询问 i | a₁ + i | gcd(a₁+i, g) = gcd(a₁+i, 3) | 答案 |
|---|---|---|---|
| 1 | 6 + 1 = 7 | gcd(7, 3) | 1 |
| 2 | 6 + 2 = 8 | gcd(8, 3) | 1 |
| 3 | 6 + 3 = 9 | gcd(9, 3) | 3 |
输出 1、1、3 ✓ 与样例一致
gcd(9, 3) = 3 一步就得到了,不用把 5 个数都算一遍。差值:47 − 31 = 16、59 − 31 = 28 → g = gcd(16, 28) = 4。
| 询问 i | a₁ + i | gcd(a₁+i, 4) | 答案 |
|---|---|---|---|
| 1 | 32 | gcd(32, 4) = 4 | 4 |
| 2 | 33 | gcd(33, 4) = 1 | 1 |
| 3 | 34 | gcd(34, 4) = 2 | 2 |
| 4 | 35 | gcd(35, 4) = 1 | 1 |
| 5 | 36 | gcd(36, 4) = 4 | 4 |
输出 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(所有差值))。这是"更相减损术"的直接应用。先算 g = gcd(所有 a_j − a_1),每组询问只需 gcd(a_1+i, g)
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 也能自然处理。对每个 i,遍历所有 n 个数求 gcd
| 方案 | 总复杂度 | n = q = 10⁵ 时 |
|---|---|---|
| 预处理差值 | O((n+q) log A) | 约 3 × 10⁶(可行) |
| 每组重算 | O(nq log A) | 约 10¹⁰(超时) |
第一行输入数组 a,第二行输入 q,程序会预留差值 gcd 并逐组给出答案。
点按钮开始 →
#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 的值和答案可能较大 |
g 初值取了 a[2]-a[1] 而不是 0,导致 n = 1 时出错;③ 用 int 但数值范围较大。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
5 3 | 1 1 3 | 题面样例 1 |
3 5 | 4 1 2 1 4 | 题面样例 2 |
1 3 | 8 9 10 | n = 1 时 g = 0,答案就是 a₁ + i |
2 2 | 6 7 | 两个数相同,差值 0,g = 0,答案即 a₁ + i |
3 2 | 3 4 | 差值 2、4 → g = 2;gcd(3,2)=1…需按公式算 |
gcd(0,x)=x),否则 n = 1 时无法处理。需要存下数组 a(用于计算差值)。
✅ 约 300 万次运算,瞬间完成。相比 O(nq) 的 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) | 多次询问类题目 |
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。)