QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#612136 | #9426. Relearn through Review | yyyyxh | ML | 1ms | 9720kb | C++14 | 1.7kb | 2024-10-05 08:25:48 | 2024-10-05 08:25:49 |
Judging History
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...