关于某道gcd题暴力优化的研究

题目描述

有 n 个数字 a[1],a[2]…a[n]。

求 max{gcd(ai,aj)} ( i!=j ) 。

n ≤ 10000 n \leq 10000 n≤10000

a i ≤ 1000000 a_i \leq 1000000 ai​≤1000000

这题std很好想，如下：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n;
int d[1000005];
int main(){
	freopen("gcd.in","r",stdin);
	freopen("gcd.out","w",stdout);
	scanf("%d",&n);
	for(int i=1,x;i<=n;i++) scanf("%d",&x),d[x]++;
	int ans=0;
	for(int i=1000000;;i--){
		int num=0;
		for(int j=1;j*i<=1000000;j++){
			num+=d[j*i];
		}
		if(num>1) {
			ans=i;
			break;
		}
	}
	printf("%d\n",ans);
	return 0;
}
           

但正如题目写的，我们要研究暴力的优化。

这是普通暴力：

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define N 10010
using namespace std;

int gcd(int a,int b) {
	return (b==0 ? a : gcd(b,a%b));
}

inline bool cmp(const int &x,const int &y) {
	return x>y;
}

int n,a[N];

int main() {
	freopen("gcd.in","r",stdin);
	freopen("gcd.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++) {
		scanf("%d",&a[i]);
	}
	register int ans=0;
	for(int i=1;i<n;i++) {
		for(register int j=i+1;j<=n;j++) {
			ans=max(ans,gcd(a[i],a[j]));
		}
	}
	printf("%d\n",ans);
	return 0;
}
           

直接暴力显然是过不了的。

但是，我们可以先从大到小排序，然后发现当 a i a_i ai​或 a j a_j aj​比 a n s ans ans小时，一定不是最优解，而且之后的数都不会比 a n s ans ans大，所以我们可以直接退出。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define N 10010
using namespace std;

int gcd(int a,int b) {
	return (b==0 ? a : gcd(b,a%b));
}

inline bool cmp(const int &x,const int &y) {
	return x>y;
}

int n,a[N];

int main() {
	freopen("gcd.in","r",stdin);
	freopen("gcd.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++) {
		scanf("%d",&a[i]);
	}
	register int ans=0;
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<n;i++) {
		if(a[i]<=ans) break; //卡常1
		for(register int j=i+1;j<=n;j++) {
			if(a[j]<=ans) break;  //卡常1
			ans=max(ans,gcd(a[i],a[j]));
		}
	}
	printf("%d\n",ans);
	return 0;
}
           

这样写对随机数据表现很好，可以跑到 0.01 0.01 0.01 秒左右，主要是因为很容易出现相同的数，使答案大于 900000 900000 900000 。但是如果我们设计一个没有相同 a i a_i ai​ 的数据，就会被卡到一秒以外。

于是，一位天才的卡常选手加了一个优化。他将 g c d gcd gcd 改为如下形式：

int gcd(int a,int b) {
	if(a<=ans) return 1;  //相当简单的一句话，但是可以把时间卡到0.3秒左右
	return (b==0 ? a : gcd(b,a%b));
}
           

但是还不够好，暴力就是要碾标算才能体现它的价值。

通过多次实验发现，没有重复数据时，答案在 400000 − 500000 400000-500000 400000−500000之间，显然是出现了一个 a i > 400000 a_i>400000 ai​>400000，且存在 a j = 2 ∗ a i a_j = 2*a_i aj​=2∗ai​，于是针对这种数据进行玄学：

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define N 10010
using namespace std;

int n,a[N],v[1000010],ans;

int gcd(int a,int b) {
	if(a<=ans) return 1;
	return (b==0 ? a : gcd(b,a%b));
}

inline bool cmp(const int &x,const int &y) {
	return x>y;
}

inline int max(int x,int y) {
	return x>y ? x : y;
}

int main() {
	freopen("gcd.in","r",stdin);
	freopen("gcd.out","w",stdout);
	scanf("%d",&n);
	ans=0;
	memset(v,0,sizeof v);
	for(int i=1;i<=n;i++) {
		scanf("%d",&a[i]);
		v[a[i]]++;
		if(v[a[i]]>1 && a[i]>ans) ans=a[i];
	}
	sort(a+1,a+n+1,cmp);
	for(int i=500000;i>=1;i--) {
		if(ans>i) break;
		if(v[i]>0 && v[i*2]>0 && ans<i) {
			ans=i;		//玄学出奇迹
			break;
		}
	}
	for(int i=1;i<n;i++) {
		if(a[i]/2<=ans) break;   //注释1
		for(register int j=i+1;j<=n;j++) {
			if(a[j]<=ans) break;
			ans=max(ans,gcd(a[i],a[j]));
		}
	}
	printf("%d\n",ans);
	return 0;
}
           

注释1：在这里 a i a_i ai​表示较大的数，如果 a i a_i ai​出现了两次以上，则可以退出；如果只有一个 a i a_i ai​，则 gcd ⁡ ( a i , a j ) \gcd (a_i,a_j) gcd(ai​,aj​) 不会超过 a i / 2 a_i/2 ai​/2。这也是一个比较有用的优化。

这个程序耗时在 0.01 s 0.01s 0.01s 左右，与标算相似，超过 O ( n ∗ n ) O(n* \sqrt n) O(n∗n

​) 算法，这可以算是玄学卡常的阶段性胜利。