企业官网建设流程全解析

题目背景

对应的选择、判断题：试题 - GESP 202506 C++ 五级 - 洛谷有题

题目描述

对于两个正整数 a,b，他们的最大公因数记为 gcd(a,b)。对于 k>3 个正整数 c1​,c2​,…,ck​，他们的最大公因数为：

gcd(c1​,c2​,…,ck​)=gcd(gcd(c1​,c2​,…,ck−1​),ck​)

给定 n 个正整数 a1​,a2​,…,an​ 以及 q 组询问。对于第 i(1≤i≤q) 组询问，请求出 a1​+i,a2​+i,…,an​+i 的最大公因数，也即 gcd(a1​+i,a2​+i,…,an​+i)。

输入格式

第一行，两个正整数 n,q，分别表示给定正整数的数量，以及询问组数。

第二行，n 个正整数 a1​,a2​,…,an​。

输出格式

输出共 q 行，第 i 行包含一个正整数，表示 a1​+i,a2​+i,…,an​+i 的最大公因数。

输入输出样例

输入 #1复制

5 3 6 9 12 18 30

输出 #1复制

1 1 3

输入 #2复制

3 5 31 47 59

输出 #2复制

4 1 2 1 4

说明/提示

对于 60% 的测试点，保证 1≤n≤103，1≤q≤10。

对于所有测试点，保证 1≤n≤105，1≤q≤105，1≤ai​≤1000。

代码实现：

#include <bits/stdc++.h> using namespace std; typedef long long ll; int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, q; cin >> n >> q; vector<int> a(n); for (int i = 0; i < n; i++) cin >> a[i]; int D = 0; if (n > 1) { for (int i = 1; i < n; i++) { D = gcd(D, abs(a[i] - a[0])); } } for (int i = 1; i <= q; i++) { int val = a[0] + i; if (n == 1) { cout << val << '\n'; } else { cout << gcd(D, val) << '\n'; } } return 0; }