QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#621978 | #9426. Relearn through Review | Emotion_Z | WA | 148ms | 5648kb | C++20 | 6.0kb | 2024-10-08 18:57:42 | 2024-10-08 18:57:42 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define deg( x ) cerr<<""#x"="<<x<<endl
#define endl '\n'
const int N=3e5+10;
const __int128 ONE=1;
int qmi( int base , int power , int m ){
int re=1;
while( power ){
if( power&1 ){
re=( ONE*re*base )%m;
}
power>>=1;
base=( ONE*base*base )%m;
}
return re;
}
int ut12[ 12 ]={ 2,3,5,7,11,13,17,19,23,29,31,37 };
bool Miller_Rabin( int n ){
if( n<=37 ){
for( int i=0; i<=11; i++ ) if( n==ut12[ i ] ) return true;
return false;
}
if( ( n&1 )^1 ) return false;
int u=n-1; int t=0;
while( ( u&1 )^1 ) u>>=1, t++;
for( int i=0; i<=11; i++ ){
int a=qmi( ut12[ i ] , u , n );
if( a==1 || a==n-1 ) continue;
for( int e=1; e<=t; e++ ){
a=( ONE*a*a )%n;
if( a==n-1 && e!=t ){ a=1; break; }
if( a==1 ) return false;
}
if( a^1 ) return false;
}
return true;
}
mt19937 rnd( chrono::steady_clock::now().time_since_epoch( ).count() );
int gcd( int a , int b ){
if( b==0 ) return a;
return gcd( b , a%b );
}
int f( int x , int c , int m ){
int re=( ( ONE*x*x )%m + ONE*c )%m;
return re;
}
int Pollard_Rho( int n ){
if( n==4 ) return 2;
if( Miller_Rabin( n ) ) return n;
while( 1 ){
int c=rnd()%( n-1 )+1;
int t=0 , r=0;
int p=1;
do{
for( int i=1; i<=128; i++ ){
t=f( t , c , n ); r=f( f( r , c , n ) , c , n );
int te=( ONE*p*abs( t-r ) )%n;
if( te==0 ) break;
p=te;
}
int d=gcd( p , n );
if( d>1 ) return d;
}while( t!=r );
}
}
int rho[ N ]; int idxr=0;
void get_fac( int n ){
idxr=0;
if( n<=1000 ){
for( int i=2; i*i<=n; i++ ){
while( n%i==0 ) n/=i , rho[ ++idxr ]=i;
}
if( n^1 ) rho[ ++idxr ]=n;
}
else{
queue<int> q;
q.push( n );
while( !q.empty() ){
int te=q.front(); q.pop();
int o=Pollard_Rho( te );
if( o==te ) rho[ ++idxr ]=o;
else q.push( o ) , q.push( te/o );
}
}
sort( rho+1 , rho+1+idxr );
}
int idx=0 , idn=0;
int fac[ N ] , num[ N ], fan[ N ];
void dec( int x ){
idx=0;
get_fac( x );
int e=1;
while( e<=idxr ){
int te=rho[ e ];
int cnt=0;
while( rho[ e ]==te ){
cnt++;
e++;
if( e==idxr+1 ) break;
}
fac[ ++idx ]=te , num[ idx ]=cnt;
}
idn=1; fan[ 1 ]=1;
for( int i=1; i<=idx; i++ ){
int en=idn , te=1;
int now=fac[ i ];
for( int k=1; k<=num[ i ]; k++ ){
te*=now;
for( int j=1; j<=en; j++ ) fan[ ++idn ]=fan[ j ]*te;
}
}
sort( fan+1 , fan+1+idn );
}
int A[ N ];
int up[ N ];
int ne[ N ];
void solve(){
int n,k;
cin>>n>>k;
A[ n+1 ]=0;
for( int i=1; i<=n; i++ ){
cin>>A[ i ];
}
for( int i=1; i<=n; i++ ){
up[ i ]=gcd( up[ i-1 ] , A[ i ] );
}
for( int i=n; i>=1; i-- ){
ne[ i ]=gcd( ne[ i+1 ] , A[ i ] );
}
int ans=0;
int cnt=0;
int cnt2=0;
for( int i=1; i<=n; i++ ){
cnt=gcd( cnt , A[ i ] );
cnt2=gcd( cnt2 , A[ i ]+k );
}
ans=max( max( cnt , cnt2 ) , ans );
cnt=0;
for( int i=1; i<=n; i++ ){
ans=max( ans , gcd( cnt , ne[ i ] ) );
cnt=gcd( cnt , A[ i ]+k );
}
cnt=0;
for( int i=n; i>=1; i-- ){
ans=max( ans , gcd( up[ i ] , cnt ) );
cnt=gcd( cnt , A[ i ]+k );
}
// 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 );
// }
// }
int te=gcd( A[ 1 ] , A[ n ] );
vector<int> V;
int oo=te;
for( int i=1; i<=n; i++ ){
oo=gcd( oo , A[ i ] );
V.emplace_back( oo );
}
oo=te;
for( int i=n; i>=1; i-- ){
oo=gcd( oo , A[ i ] );
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 ];
bool ok=false;
int l=1;
for( ; l<=n; l++ ){
if( A[ l ]%now != 0 ){
if( ( A[ l ]+k )%now == 0 ) break;
else{
ok=true;
break;
}
}
}
if( ok ) continue;
int r=l+1;
for( ; r<=n; r++ ){
if( ( A[ r ]+k )%now!=0 ){
if( A[ r ]%now==0 ) break;
else{
ok=true;
break;
}
}
}
if( ok ) continue;
for( int e=r; e<=n; e++ ){
if( A[ e ]%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: 5648kb
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: 148ms
memory: 3648kb
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'