#C231108A. 最大公约数(gcd)

前言（Front talk)

我也不知道为什么这样打会是最优解，当时做题的时候我甚至还在思考到底能不能过，结果这玩意儿就跑完了，我还搁哪想了半天更优解。(￣_￣|||)

网址（Website）

题目详情 - 最大公约数(gcd) - Super

题解 - 最大公约数(gcd) - Super

题解（Solution）

讲一下倒着来做的做法，将每个放进一个值域里面（这道题的数据范围救了我），然后倒着寻找可能的最大，用数组分别记录是数组中多少个数的约数，由于有的限制，我们用数组和数组来维护这些约数在数组中的最大位置和最小位置，如果且则可以作为最大的最大公约数，直接退出循环，输出即可。

实际上数组根本不用维护，因为如果当前只有一个，那么一定等于，不会满足的条件，因为数据范围中。

代码（Code）

我的代码

实际上速度比题解还快，因为不是严格的。

目前试出来最快是总共，相较于正解的不知道优化了多少。

#include<bits/stdc++.h> 
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
char buf[100],*p1=buf,*p2=buf;
inline int gc(){ return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100,stdin),p1==p2)?EOF:*p1++; }
inline int input(){
	int x=0; char ch=gc(); bool f=1;
	while(!isdigit(ch)) f^=ch=='-',ch=gc();
	while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=gc();
	return f?x:-x;
}
const int M = 1012345;
const int N = 301234;
int n,k,a[N];
bitset<M> hav;
int sum[N];
int ma[M],mi[M];

signed main(){
	string str("gcd");
	freopen((str+".in").c_str(),"r",stdin);
	freopen((str+".out").c_str(),"w",stdout); 
	memset(mi,0x3f,sizeof(mi));
	n=input(),k=input();For(i,1,n){
		a[i]=input();
		ma[a[i]]=max(ma[a[i]],i);
		mi[a[i]]=min(mi[a[i]],i);
		hav[M-a[i]]=true;
	}int i,p,w;
	for(i=hav._Find_first();M-i<=M;i=hav._Find_next(i)){
		p=M-i;if(ma[p]-mi[p]>=k) return cout<<p<<'\n',0;
		int q=(int)sqrt(p);
		for(int j=2;j<=q;++j){
			if(p%j==0){w=p/j;
				ma[j]=max(ma[j],ma[p]);
				mi[j]=min(mi[j],mi[p]);
				ma[w]=max(ma[w],ma[p]);
				mi[w]=min(mi[w],mi[p]);
				hav[M-j]=true,hav[M-w]=true;
			}
		}
	}return 0;
}

题解代码

还是把题解的加上吧，题解是正着来的。

#include <iostream>
#include <cstdio>
#define maxn 1000000
using namespace std;
int n,k,a[300005];
int mn[1000005],mx[1000005];
int ans;
int main(){
	freopen("gcd.in","r",stdin);
	freopen("gcd.out","w",stdout);
	scanf("%d%d",&n,&k);
	for (int i=1;i<=maxn;i++)mn[i]=n+1,mx[i]=0;
	for (int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		mn[a[i]]=min(mn[a[i]],i);
		mx[a[i]]=max(mx[a[i]],i);
	}
	for (int i=1;i<=maxn;i++){
		int l=n+1,r=0;
		for (int j=i;j<=maxn;j+=i){
			l=min(l,mn[j]);
			r=max(r,mx[j]);
		}
		if (r-l>=k)ans=i;
	}
	printf("%d\n",ans);
	return 0;
}

后续（Ending）

时间证明：

代码：

这个是 superl61 的代码，按照我的方法打的。

博客网址： superl61

#include<cstdio>
#include<ctype.h>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<bitset>
#define F(i,l,r) for(register int i=l;i<=r;++i)
#define G(i,r,l) for(register int i=r;i>=l;--i)
using std::min;
using std::max;
char buf[30],*p1=buf,*p2=buf;
inline int gc(){ return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,30,stdin),p1==p2)?EOF:*p1++; }
inline int rd(){
	int x=0; char ch=gc();
	while(!isdigit(ch)) ch=gc();
	while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=gc();
	return x;
}
const int M=1e6+5;
int n,k,x,mi[M],ma[M];
std::bitset<M> b;
int main(){
	freopen("gcd.in","r",stdin);
	freopen("gcd.out","w",stdout);
	n=rd(),k=rd(),memset(mi,0x3f,sizeof(mi));
	F(i,1,n) {
		x=rd();
		mi[x]=min(mi[x],i);
		ma[x]=max(ma[x],i);	
		b[M-x]=1;
	}
	for(int i=b._Find_first();M-i<=M;i=b._Find_next(i)){ 
		int p=M-i;
		if(ma[p]-mi[p]>=k) return printf("%d\n",p),fflush(0),fclose(stdin),fclose(stdout),0; 
		int q=(int)sqrt(p);
		F(j,2,q) if(!(p%j)){
			b[M-j]=b[M-p/j]=1;
			mi[j]=min(mi[j],mi[p]),ma[j]=max(ma[j],ma[p]);
			mi[p/j]=min(mi[p/j],mi[p]),ma[p/j]=max(ma[p/j],ma[p]);
		}
	}
	puts("1");
	fflush(0),fclose(stdin),fclose(stdout);
	return 0;
}