Categories
Uncategorized

J Heritage of Skywalkert

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

Topic:

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

Time limit: C/C++ 1 second, other languages 2 seconds
Space limit: C/C++ 262144K, other languages 524288K
64bit IO Format: %lld

题目描述

skywalkert, the new legend of Beihang University ACM-ICPC Team, retired this year leaving a group of newbies again.

Rumor has it that he left a heritage when he left, and only the one who has at least 0.1% IQ(Intelligence Quotient) of his can obtain it.

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)

The n integers are obtained by calling the following function n times, the i-th result of which is ai, and we ensure all ai > 0. Please notice that for each test case x, y and z should be reset before being called.
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.
Example 1

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:

#include
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 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; }

 

Leave a Reply