2018牛客多校 J Heritage of skywalkert

我先猜了个结论，结尾两个数字lcm就是答案，然后WA了，之后就开始研究这个序列，发现n=100的时候答案在64 和 96大的数字的lcm取到，于是就否定了我之前的猜想，于是我开始研究这个数列，打1e6的表，看有没有顺序，有没有一样的数字，然后我发现没顺序，有一样的数字，接着想到我只要找到一个比较大的质数和最后一个数字撑起来就行了，于是我打表找了一下最大的质数一般在第几大，于是突然发现最大的质数离边界都很近。。。。我想能不能去最大的一些数字中暴力找最大的lcm，于是使用了nth_element,再暴力跑最大的2000个数字，T掉，改成100个就过了。玄学题啊，因为质数出现的几率是比较大的，所以互质的数再最大的100个中一般能找到。

#include<cstdio>
#include<algorithm>
#define maxl 10000010
#define ull unsigned long long
  
using namespace std;
 
int cas;
int n;
ull ans;
unsigned int A,B,C,x,y,z;
ull a[maxl];
 
inline long long tang()
{
    unsigned int t;
    x^=x<<16;
    x^=x>>5;
    x^=x<<1;
    t=x;x=y;y=z;
    z=t^x^y;
    return z;
}
 
inline void prework()
{
    scanf("%d%u%u%u",&n,&A,&B,&C);
    x=A;y=B,z=C;
    for(int i=1;i<=n;i++)
        a[i]=tang();
}
 
inline unsigned int gcd(unsigned int a,unsigned int b)
{
    if(b==0)
        return a;
    else
        return gcd(b,a%b);
}
 
inline void mainwork()
{
    nth_element(a+1,a+n-100,a+n+1);
 ans=0;
    for(int i=max(1,n-100);i<=n;i++)
        for(int j=i+1;j<=n;j++)
        {
            ull t=a[i]*a[j]/gcd(a[i],a[j]);
            if(ans<t)
                ans=t;
        }
 
}
 
inline void print()
{
    printf("Case #%d: %llu\n",cas,ans);
}
 
int main()
{
    int t;
    scanf("%d",&t);
    for(cas=1;cas<=t;cas++)
    {
        prework();
        mainwork();
        print();
    }
    return 0;
}