题目描述
对于两个正整数 a,ba,ba,b，他们的最大公因数记为 gcd(a,b)\gcd(a,b)gcd(a,b)。对于 k>3k > 3k>3 个正整数 c1,c2,…,ckc_1,c_2,\dots,c_kc1,c2,…,ck，他们的最大公因数为：
gcd(c1,c2,…,ck)=gcd(gcd(c1,c2,…,ck−1),ck)\gcd(c_1,c_2,\dots,c_k)=\gcd(\gcd(c_1,c_2,\dots,c_{k-1}),c_k)gcd(c1,c2,…,ck)=gcd(gcd(c1,c2,…,ck−1),ck)
给定 nnn 个正整数 a1,a2,…,ana_1,a_2,\dots,a_na1,a2,…,an 以及 qqq 组询问。对于第 i(1≤i≤q)i(1 \le i \le q)i(1≤i≤q) 组询问，请求出 a1+i,a2+i,…,an+ia_1+i,a_2+i,\dots,a_n+ia1+i,a2+i,…,an+i 的最大公因数，也即 gcd(a1+i,a2+i,…,an+i)\gcd(a_1+i,a_2+i,\dots,a_n+i)gcd(a1+i,a2+i,…,an+i)。
输入格式
第一行，两个正整数 n,qn,qn,q，分别表示给定正整数的数量，以及询问组数。
第二行，nnn 个正整数 a1,a2,…,ana_1,a_2,\dots,a_na1,a2,…,an。
输出格式
输出共 qqq 行，第 iii 行包含一个正整数，表示 a1+i,a2+i,…,an+ia_1+i,a_2+i,\dots,a_n+ia1+i,a2+i,…,an+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%60\%60% 的测试点，保证 1≤n≤1031 \le n \le 10^31≤n≤103，1≤q≤101 \le q \le 101≤q≤10。
对于所有测试点，保证 1≤n≤1051 \le n \le 10^51≤n≤105，1≤q≤1051 \le q \le 10^51≤q≤105，1≤ai≤10001 \le a_i \le 10001≤ai≤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;}}结果
上安装使用同花顺远航版)
