Summer ACM Multi School Camp (Session 6) J Heritage of Skywalkert

Topic:

Link: https://www.nowcoder.com/acm/contest/144/J来源：牛客网

Space limit: C/C++ 262144K, other languages 524288K

64bit IO Format: %lld

## 题目描述

To prove you have at least 0.1% IQ of skywalkert, you have to solve the following problem:

Given n positive integers, for all (i, j) where 1 ≤ i, j ≤ n and i ≠ j, output the maximum value among . means the Lowest Common Multiple.

Enter Description:

The input starts with one line containing exactly one integer t which is the number of test cases. (1 ≤ t ≤ 50)

For each test case, the first line contains four integers n, A, B, C. (2 ≤ n ≤ 10

7

, A, B, C are randomly selected in unsigned 32 bits integer range)

No more than 5 cases have n greater than 2 x 10

6

.

Output Description:

For each test case, output "Case #x: y" in one line (without quotes), where x is the test case number (starting from 1) and y is the maximum lcm.

Enter

Copy

2 2 1 2 3 5 3 4 8

Output

Copy

Case #1: 68516050958 Case #2: 5751374352923604426

Ideas:

Call the given function tang (), generate the number a [1] to a [n], then call the library function nth_element of STL (the principle is fast row, you can also hand rub), select the top 100 number, then force choose two numbers, making the minimum common multiples the maximum.

Attached:

Regarding the use of the nth_element () method in STL: by calling the nth_element (start, start+n, end) method, you can make the nth largest element in the nth position (starting from 0, where the position is the element subscript n), and the smaller elements than this element are listed before this element, larger than this element All prime are ranked in after this element, but there is no guarantee that they are ordered.

Code:

#includeusing 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 vec; int num=min(n,100); nth_element(a+1,a+1+n-num,a+1+n); ///只要排一次 /// Select the top 100 number

for(int k=1;k<=num;k++){ vec.push_back(a[n+1-k]); } ///Violent looking lcm Max

ull ans=0; for(int i=0;i){ for(int j=i+1;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< endl; } return 0; }