QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#640592 | #9426. Relearn through Review | Nuj# | WA | 202ms | 9840kb | C++14 | 1.5kb | 2024-10-14 14:32:51 | 2024-10-14 14:32:51 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define endl '\n'
#define dbg(x) cerr<<"In Line "<<__LINE__<<' '<<#x<<" = "<<(x)<<endl
ll a[300005],pre[300005],suf[300005],b[300005],c[300005],ans,k;
void solve(int l,int r,ll now){
if(l==r) return ;
int mid=l+r>>1;
pre[l-1]=suf[mid+1]=0;
int cntl=0,cntr=0;
for(int i=l;i<=mid;i++) pre[i]=__gcd(pre[i-1],abs(a[i]));
for(int i=mid;i>=l;i--) suf[i]=__gcd(suf[i+1],abs(a[i]));
for(int i=l;i<=mid;i++) b[++cntl]=__gcd(pre[i-1],__gcd(suf[i+1],abs(a[i]+k)));
pre[mid]=suf[r+1]=0;
for(int i=mid+1;i<=r;i++) pre[i]=__gcd(pre[i-1],abs(a[i]));
for(int i=r;i>=mid;i--) suf[i]=__gcd(suf[i+1],abs(a[i]));
for(int i=mid+1;i<=r;i++) c[++cntr]=__gcd(pre[i-1],__gcd(suf[i+1],abs(a[i]-k)));
sort(b+1,b+cntl+1),cntl=unique(b+1,b+cntl+1)-b-1;
sort(c+1,c+cntr+1),cntr=unique(c+1,c+cntr+1)-c-1;
for(int i=1;i<=cntl;i++) for(int j=1;j<=cntr;j++) ans=max(ans,__gcd(now,__gcd(b[i],c[j])));
solve(l,mid,__gcd(now,suf[l])),solve(mid+1,r,__gcd(now,pre[r]));
}
int main(){
cin.tie(0)->sync_with_stdio(0);
int t;cin>>t;
while(t--){
int n;cin>>n>>k,ans=1;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=n;i;i--) a[i]-=a[i-1];
for(int i=1;i<=n;i++) pre[i]=__gcd(pre[i-1],abs(a[i]));
suf[n+1]=0;for(int i=n;i;i--) suf[i]=__gcd(suf[i+1],abs(a[i]));
for(int i=1;i<=n;i++) ans=max(ans,__gcd(pre[i],__gcd(suf[i],abs(a[i]+k))));
// for(int i=1;i<=n;i++) cout<<a[i]<<' ';cout<<endl;
solve(1,n,0),cout<<ans<<endl;
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 9760kb
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
Wrong Answer
time: 202ms
memory: 9840kb
input:
100000 1 608611451460421713 33155506392034032 1 743116173559300609 6138108577573005 7 364454564010802125 657035115675878115 657035115675878115 657035115675878115 657035115675878115 657035115675878115 292580551665075990 657035115675878115 4 316648374341335221 365788422120542814 182894211060271407 731...
output:
3 1 364454564010802125 3 1 2 183698346865682381 1 4 6 2 3 25 37337367838628559 105293193934201213 377121713907330928 2 1 2 2 4 67011127049073692 1 1 809535299113892268 3 1 1 1 1 3 1 4 557547233762973087 3 3 2 777819466140221104 349510709206402782 263603028342631011 2 926534262599314442 7063313119016...
result:
wrong answer 1st lines differ - expected: '641766957852455745', found: '3'