简答题
偏难
#20268
最大公因数 时间限制:1 s,内存限制:512 MB 【问题描述】 对于两个正整数 a、b,它们的最大公因数记为 gcd(a, b)。对于 k >=3 个正整数…
最大公因数
时间限制:1 s,内存限制:512 MB
【问题描述】
对于两个正整数 a、b,它们的最大公因数记为 gcd(a, b)。对于 k >=3 个正整数 c1、c2、……、ck,它们的最大公因数为:
gcd(c1, c2, ……, ck) = gcd(gcd(c1, c2, ……, c(k-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】
【样例输出1】
【样例输入2】
【样例输出2】
【数据范围】
对于60%的测试点,保证 1 <= n <= 1000,1 <= q <= 10。
对于所有测试点,保证 1 <= n、q <= 10^5,1 <= ai <= 1000。
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 5;
int n, q, a[N], g;
int gcd(int a, int b) {
if (a == 0 || b == 0)
return a + b;
return gcd(b, a % b);
}
int main() {
cin >> n >> q;
for (int i = 1; i <= n; i++)
cin >> a[i];
sort(a + 1, a + n + 1);
for (int i = 2; i <= n; i++)
g = gcd(g, a[i] - a[i - 1]);
for (int i = 1; i <= q; i++)
cout << gcd(g, a[1] + i) << endl;
return 0;
}</pre>
这道题暂未补解析。