QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#621978#9426. Relearn through ReviewEmotion_ZWA 148ms5648kbC++206.0kb2024-10-08 18:57:422024-10-08 18:57:42

Judging History

你现在查看的是最新测评结果

  • [2024-10-08 18:57:42]
  • 评测
  • 测评结果:WA
  • 用时:148ms
  • 内存:5648kb
  • [2024-10-08 18:57:42]
  • 提交

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'