牛客网暑期ACM多校训练营（第六场） J    Heritage of skywalkert

题意不说了

 

思路,unsigned int就够了. 题目本来就会自然溢出,那么,,,就溢出好了,结果发现溢出后的数都是伪随机数.

nth_element O(n) 找前100个最大的 (原来还真有故意让溢出的题啊

暴力

#include<cstdio>
#include<vector>
#include<cmath>
#include<string>
#include<queue>
#include<set>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<map>
#define PI acos(-1.0)
#define pb push_back
#define F first
#define S second
using namespace std;
//typedef long long ll;
typedef unsigned long long ll;
typedef unsigned int ui;
const int N=1e7+7;
const int MOD=998244353;
template <class T>
bool sf(T &ret){ //Faster Input
    char c; int sgn; T bit=0.1;
    if(c=getchar(),c==EOF) return 0;
    while(c!='-'&&c!='.'&&(c<'0'||c>'9')) c=getchar();
    sgn=(c=='-')?-1:1;
    ret=(c=='-')?0:(c-'0');
    while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
    if(c==' '||c=='\n'){ ret*=sgn; return 1; }
    while(c=getchar(),c>='0'&&c<='9') ret+=(c-'0')*bit,bit/=10;
    ret*=sgn;
    return 1;
}
ll ans[N];
int ks;
bool cmp(ll a,ll b){
    return a>b;
}
void mian(){
//    cout <<(ll)-1<<endl;
//    cout <<"5751374352923604426"<<endl;
    ll n,a,b,c;
    cin >>n>>a>>b>>c;
    ui x,y,z;
    x=a,y=b,z=c;

    for(ll i=1;i<=n;i++){1
        ui t;
        x^=x<<16;
        x^=x>>5;
        x^=x<<1;
        t=x;
        x=y;
        y=z;
        z=t^x^y;
        ans[i]=z;
    }
//    for(int i=1;i<=n;i++)   cout << ans[i]<<" ";
//    cout << endl;

    nth_element(ans+1,ans+min((ll)100,n),ans+n,cmp);
    ll mx=0;
    for(int i=1;i<=min((ll)100,n);i++){
        for(int j=i+1;j<=min((ll)100,n);j++){
            ll GCD=__gcd(ans[i],ans[j]);
//            cout <<GCD<<endl;
            if(ans[i]/GCD*ans[j]>mx){
                mx=ans[i]/GCD*ans[j];
            }
        }
    }
    printf("Case #%d: ",++ks);
    cout << mx << endl;
}

int main(void){
    int T;
    sf(T);
    while(T--){
        mian();
    }

    return 0;
}