QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#693733 | #9426. Relearn through Review | Nana7# | WA | 288ms | 3704kb | C++14 | 1.3kb | 2024-10-31 16:39:38 | 2024-10-31 16:39:41 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<map>
#include<algorithm>
#define I inline
#define int long long
using namespace std;
const int N = 300010;
int a[N];
int n,k;
vector<int> g;
map<int,int> mp;
int gcd(int x,int y) {
if(!y) return x;
return gcd(y,x%y);
}
I bool check(int x) {
int cnt=0;
for(int i=1;i<=n;++i) if(a[i]%x!=0) cnt++;
if(!cnt) return 1;
if(k%x==0) return 0;
for(int i=1;i<=n;++i) {
if(a[i]%x!=0&&(a[i]+k)%x!=0) return 0;
}
bool apr=0;
for(int i=1;i<=n;++i) {
if(a[i]%x!=0) {
if(apr&&(a[i-1]%x==0)) {
return 0;
}
else apr=1;
}
}
return 1;
}
I void solve() {
cin>>n>>k; g.clear(); mp.clear();
for(int i=1;i<=n;++i) cin>>a[i];
int ng=-1;
for(int i=1;i<=n;++i) {
if(ng==-1) ng=a[i];
else ng=gcd(a[i],ng);
if(mp[ng]==0) mp[ng]=1,g.push_back(ng);
}
ng=-1;
for(int i=n;i>=1;--i) {
if(ng==-1) ng=a[i];
else ng=gcd(a[i],ng);
if(mp[ng]==0) mp[ng]=1,g.push_back(ng);
}
int ans=1;
for(auto &t:g) {
if(check(t)) ans=max(ans,t);
}
for(int i=1;i<=n;++i) a[i]+=k;
ng=a[1];
for(int i=2;i<=n;++i) ng=gcd(ng,a[i]);
ans=max(ans,ng);
cout<<ans<<endl;
}
signed main()
{
int T; cin>>T;
while(T--) {
solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3692kb
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: 288ms
memory: 3704kb
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 657035115675878115 182894211060271407 880411769063535667 560553564512176618 1 962990836390050009 616597869896951268 878097339332572161 188820994675344528 997057718507559252 949074379610491450 2 632093288650732211 1 356502546608886970 789177332497135009 566104642...
result:
wrong answer 7th lines differ - expected: '183698346865682381', found: '1'