牛客第六场 J.Heritage of skywalkert（On求前k大）

题目传送门：https://www.nowcoder.com/acm/contest/144/J

题意：给一个function，构造n个数，求出其中任意两个的lcm的最大值。

分析：要求最大的lcm，大概分析一下，差不多就在里面的最大的k个里，k^2求出答案。

因为n（1e7），sort会tle，需要一个效率更低的排序来求出前k大。

 #include<bits/stdc++.h>

 using namespace std;

 const int maxn=1e7+;

 typedef unsigned ui;

 typedef unsigned long long ull;

 ui x,y,z;

 ui A,B,C;

 ui a[maxn],b[maxn];

 int n;

 ui tang(){

     ui t;

     x^=x<<;

     x^=x>>;

     x^=x<<;

     t=x;x=y;y=z;z=t^x^y;

     return z;

 }

 ull gcd(ull x,ull y){

     if (y==) return x;

     else return gcd(y,x%y);

 }

 void _sort(int k,int l,int r){

     ui kk=a[(l+r)/];

     int i=l,j=r;

     while (i<j){

         while (a[j]>kk) j--;

         while (a[i]<kk) i++;

         if (i<=j){

             swap(a[i],a[j]);

             i++;j--;

         }

     }

     if (r-i+==k) return ;

     else if (r-i+>k) _sort(k,i+,r);

     else _sort(k-(r-i+),l,i-);

 }

 int main(){

     ios::sync_with_stdio(false);

     cin.tie();cout.tie();

     int t;

     cin >> t;

     for (int id=;id<=t;id++){

         cin >> n >> A >> B >> C;

         x=A;y=B;z=C;

         for (int i=;i<n;i++){

             a[i]=tang();

         }

         ull ans=;

         int k=min(n,);

         _sort(k,,n-);

         int cnt=;

         for (int i=n-;i>=n-k;i--)

             b[cnt++]=a[i];

         for (int i=;i<cnt;i++){

             for (int j=i+;j<cnt;j++){

                 ull _gcd;

                 if (b[i]>b[j]) _gcd=gcd(b[i],b[j]);

                 else _gcd=gcd(b[j],b[i]);

                 ans=max(ans,b[i]/_gcd*b[j]);

             }

         }

         cout << "Case #" << id << ": " << ans << endl;

     }

     return ;

 }