题解：P13014 [GESP202506 五级] 最大公因数

题意

给定

n

个正整数

a_1,a_2,\dots,a_n

以及

q

组询问。对于第

i(1 \le i \le q)

组询问，求出

\gcd(a_1+i,a_2+i,\dots,a_n+i)

。然而暴力会 TLE。

方法

注意到最大公因数有以下性质：

\gcd(a_1+i, a_2+i, \dots, a_n+i) = \gcd(a_1+i, (a_2 - a_1), (a_3 - a_1), \dots, (a_n - a_1))

这是因为：

\gcd(a+i, b+i) = \gcd(a+i, (b+i) - (a+i)) = \gcd(a+i, b-a)

这个性质可以推广到多个数的情况。

所以计算所有

a_j - a_1

（

j \geq 2

）的最大公因数，记为

d

。这样就将问题简化为计算

\gcd(a_1 + i, d)

。对于每个查询

i

，计算该柿子即可。

最后直接输出结果。

代码

CPP

#include<bits/stdc++.h>
using namespace std;
int n, q,a[100005],d;
int main() {
	scanf("%d%d",&n,&q);
	for (int i=1;i<=n;i++)
		scanf("%d", &a[i]);
	sort(a+1,a+n+1);
	for (int i=2;i<=n;i++)
		d=__gcd(d,a[i]-a[i - 1]);//根据 gcd 的性质计算 d
	for (int i=1;i<=q;i++)
		printf("%d\n",__gcd(d,a[1]+i));//输出时直接套公式
	return 0;
}

题解：P13014 [GESP202506 五级] 最大公因数

文章操作

题意

方法

代码

相关推荐

评论

题解：P13014 [GESP202506 五级] 最大公因数