題目描述

對于兩個正整數 $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?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?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?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;
}