QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#640597 | #9426. Relearn through Review | Nuj# | WA | 192ms | 9824kb | C++14 | 1.5kb | 2024-10-14 14:36:23 | 2024-10-14 14:36:24 |
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-1],__gcd(suf[i+1],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: 9804kb
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: 192ms
memory: 9824kb
input:
100000 1 608611451460421713 33155506392034032 1 743116173559300609 6138108577573005 7 364454564010802125 657035115675878115 657035115675878115 657035115675878115 657035115675878115 657035115675878115 292580551665075990 657035115675878115 4 316648374341335221 365788422120542814 182894211060271407 731...
output:
641766957852455745 749254282136873614 364454564010802125 182894211060271407 880411769063535667 560553564512176618 183698346865682381 962990836390050009 616597869896951268 878097339332572161 188820994675344528 997057718507559252 949074379610491450 37337367838628559 105293193934201213 3771217139073309...
result:
wrong answer 3rd lines differ - expected: '657035115675878115', found: '364454564010802125'