QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#612136#9426. Relearn through ReviewyyyyxhML 1ms9720kbC++141.7kb2024-10-05 08:25:482024-10-05 08:25:49

Judging History

你现在查看的是最新测评结果

  • [2024-10-05 08:25:49]
  • 评测
  • 测评结果:ML
  • 用时:1ms
  • 内存:9720kb
  • [2024-10-05 08:25:48]
  • 提交

answer

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
template<typename T>
T read(){
	char c=getchar();T x=0;
	while(c<48||c>57) c=getchar();
	do x=x*10+(c^48),c=getchar();
	while(c>=48&&c<=57);
	return x;
}
const int N=300003;
int n;ll k;
ll a[N],res;
inline ll gcd(ll a,ll b){
	for(ll t;b;t=b,b=a%b,a=t);
	return abs(a);
}
ll pre[N],suf[N];
ll sl[N];int nl;
ll sr[N];int nr;
void sol(int l,int r,ll v){
	if(r-l==1){
		res=max(res,gcd(a[r]-a[l]+k,v));
		res=max(res,gcd(a[r]-a[l],v));
		return;
	}
	int mid=(l+r)>>1;
	ll lv=v,rv=v;
	for(int i=mid;i<r;++i) lv=gcd(lv,a[i+1]-a[i]);
	for(int i=l;i<mid;++i) rv=gcd(rv,a[i+1]-a[i]);
	sol(l,mid,lv);sol(mid,r,rv);
	suf[mid]=pre[l]=v;
	for(int i=l;i<mid;++i) pre[i+1]=gcd(pre[i],a[i+1]-a[i]);
	for(int i=mid;i>l;--i) suf[i-1]=gcd(suf[i],a[i]-a[i-1]);
	sl[nl=1]=suf[l];
	for(int i=l;i<mid;++i){
		ll val=gcd(gcd(pre[i],suf[i+1]),a[i+1]-a[i]+k);
		if(suf[l]%val==0) continue;
		sl[++nl]=val;
	}
	suf[r]=pre[mid]=v;
	for(int i=mid;i<r;++i) pre[i+1]=gcd(pre[i],a[i+1]-a[i]);
	for(int i=r;i>mid;--i) suf[i-1]=gcd(suf[i],a[i]-a[i-1]);
	sr[nr=1]=pre[r];
	for(int i=mid;i<r;++i){
		ll val=gcd(gcd(pre[i],suf[i+1]),a[i+1]-a[i]-k);
		if(pre[r]%val==0) continue;
		sr[++nr]=val;
	}
	for(int i=1;i<=nl;++i)
		for(int j=1;j<=nr;++j) res=max(res,gcd(sl[i],sr[j]));
}
void solve(){
	n=read<int>();k=read<ll>();res=0;
	for(int i=1;i<=n;++i) a[i]=read<ll>();
	pre[0]=suf[n+1]=0;
	for(int i=1;i<=n;++i) pre[i]=gcd(pre[i-1],a[i]+k);
	for(int i=n;i;--i) suf[i]=gcd(suf[i+1],a[i]);
	for(int i=0;i<=n;++i) res=max(res,gcd(pre[i],suf[i+1]));
	sol(1,n,a[1]);
	printf("%lld\n",res);
}
int main(){
	int tc=read<int>();
	while(tc--) solve();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 9720kb

input:

2
6 2
5 3 13 8 10 555
3 0
3 6 9

output:

5
3

result:

ok 2 lines

Test #2:

score: -100
Memory Limit Exceeded

input:

100000
1 608611451460421713
33155506392034032
1 743116173559300609
6138108577573005
7 364454564010802125
657035115675878115 657035115675878115 657035115675878115 657035115675878115 657035115675878115 292580551665075990 657035115675878115
4 316648374341335221
365788422120542814 182894211060271407 731...

output:


result: