https://www.cnblogs.com/longl/p/9424657.html
思路：
调用题目的给的函数tang(), 生成数a[1]到a[n], 然后调用STL的库函数nth_element(原理是快排，也可以自己手搓) ，选出前100大的数，然后暴力选两个数，使得最小公倍数最大。
关于STL中的nth_element()方法的使用：通过调用nth_element(start, start+n, end) 方法可以使第n大元素处于第n位置（从0开始,其位置是下标为 n的元素），并且比这个元素小的元素都排在这个元素之前，比这个元素大的元素都排在这个元素之后，但不能保证他们是有序的。
代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn =1e7+20;
unsigned x,y,z,A,B,C;
typedef unsigned long long ull;
unsigned a[maxn];
unsigned tang(){
unsigned t;
x^=x<<16;
x^=x>>5;
x^=x<<1;
t=x;
x=y;
y=z;
z=t^x^y;
return z;
}
int main()
{
int t,n;
cin>>t;
for(int cas=1;cas<=t;cas++){
cin>>n>>A>>B>>C;
x=A,y=B,z=C;
for(int i=1;i<=n;i++)
a[i]=tang();
vector<unsigned> vec;
int num=min(n,100);
nth_element(a+1,a+1+n-num,a+1+n); ///只要排一次
/// 选出前一百大的数
for(int k=1;k<=num;k++){
vec.push_back(a[n+1-k]);
}
///暴力找lcm最大
ull ans=0;
for(int i=0;i<vec.size();i++){
for(int j=i+1;j<vec.size();j++){
ull gcd = __gcd((ull)vec[i],(ull)vec[j]);
ull tp=vec[i]/gcd*vec[j];
ans = max(ans,tp);
}
}
printf("Case #%d: ",cas);
cout<<ans<<endl;
}
return 0;
}
全部评论
(0) 回帖