QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#625785 | #9426. Relearn through Review | WaO_o | WA | 161ms | 5708kb | C++20 | 2.9kb | 2024-10-09 21:01:30 | 2024-10-09 21:01:30 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int __int128
#define deg( x ) cerr<<""#x"="<<x<<endl
//#define endl '\n'
istream &operator>>( istream &in , __int128 &n ){
string s; in>>s;
n=0;
for(char i:s) n=n*10+i-'0';
return in;
}
ostream &operator<<( ostream &out , __int128 n ){
if( n==0 ){
out<<0;
return out;
}
string s;
while( n ){
s+='0'+n%10;
n/=10;
}
reverse( s.begin( ) , s.end( ) );
out<<s;
return out;
}
const int N=6e5+10;
int idn=0;
int fan[ N ];
int A[ N ];
int gcd( int a , int b ){
if( b==0 ) return a;
return gcd( b , a%b );
}
void solve(){
int n,k;
cin>>n>>k;
for( int i=1; i<=n; i++ ){
cin>>A[ i ];
}
int ans=0;
/*
// vector<int> V;
// V.emplace_back( 0 );
//
// int e=1;
// while( e<=n ){
// int te=A[ e ];
// while( A[ e ]==te ){
// e++;
// if( e==n+1 ) break;
// }
// V.emplace_back( te );
// }
//
// n=V.size()-1;
// for( int l=1; l<=min( n , 1ll+50 ); l++ ){
// cnt=0;
// for( int o=1; o<l; o++ ) cnt=gcd( cnt , V[ o ] );
// for( int r=max( l+1 , n-50 ); r<=n; r++ ){
// int te=cnt;
// for( int o=l; o<=r; o++ ){
// te=gcd( te , V[ o ]+k );
// }
// for( int o=r+1; o<=n; o++ ) te=gcd( te , V[ o ] );
//
// ans=max( ans , te );
// }
// }
*/
vector<int> V;
int oo=0;
for( int i=1; i<=n; i++ ){
oo=gcd( oo , A[ i ] );
V.emplace_back( oo );
}
oo=0;
for( int i=n; i>=1; i-- ){
oo=gcd( oo , A[ i ] );
V.emplace_back( oo );
}
oo=0;
for( int i=n; i>=1; i-- ){
oo=gcd( oo , A[ i ]+k );
V.emplace_back( oo );
}
oo=0;
for( int i=1; i<=n; i++ ){
oo=gcd( oo , A[ i ]+k );
V.emplace_back( oo );
}
sort( V.begin() , V.end() );
V.erase( unique( V.begin() , V.end() ) , V.end() );
idn=0;
for( auto x:V ){
fan[ ++idn ]=x;
}
for( int i=idn; i>=1; i-- ){
int now=fan[ i ];
if( now <= ans ) break;
if( now==0 ) continue;
bool ok=false;
int l=1;
for( ; l<=n; l++ ){
if( A[ l ]%now != 0 ) break;
}
int r=n;
for( ; r>=1; r-- ){
if( A[ r ]%now != 0 ) break;
}
for( int e=l; e<=r; e++ ){
if( ( A[ e ]+k )%now!=0 ){
ok=true;
break;
}
}
if( ok ) continue;
ans=max( ans , now );
}
cout<<ans<<endl;
}
signed main() {
ios::sync_with_stdio( 0 );
cin.tie( 0 ); cout.tie( 0 );
int T=1;
cin>>T;
while( T-- ){
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5584kb
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: 161ms
memory: 5708kb
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 183698346865682381 962990836390050009 616597869896951268 878097339332572161 188820994675344528 997057718507559252 949074379610491450 2 632093288650732211 377121713907330928 3565025466088...
result:
wrong answer 14th lines differ - expected: '37337367838628559', found: '2'