題目描述

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

solution

先求它們差的 gcd， 因為這個是不變的，然后用結果和第一個值求 gcd 即可

代碼

#include <iostream>
#include "bit"
#include "vector"
#include "unordered_set"
#include "unordered_map"
#include "set"
#include "queue"
#include "algorithm"
#include "bitset"
#include "cstring"using namespace std;int n, q, a;int gcd(int x, int y) {return y ? gcd(y, x % y) : x;
}int main() {cin >> n >> q;cin >> a;int g = 0, x, pre = a;for (int i = 1; i < n; i++) {cin >> x;g = gcd(g, abs(x - pre));pre = x;}for (int i = 1; i <= q; i++) {cout << gcd(g, a + i) << endl;}}

結果