/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 98ms 17.68 MiB
#2 Accepted 101ms 17.691 MiB
#3 Accepted 107ms 17.695 MiB
#4 Accepted 109ms 17.492 MiB
#5 Accepted 99ms 17.695 MiB
#6 Accepted 94ms 17.508 MiB
#7 Accepted 92ms 17.691 MiB
#8 Accepted 93ms 17.695 MiB
#9 Accepted 94ms 17.695 MiB
#10 Accepted 96ms 17.695 MiB
#11 Accepted 98ms 17.586 MiB
#12 Accepted 100ms 17.703 MiB
#13 Accepted 99ms 17.695 MiB
#14 Accepted 107ms 17.703 MiB
#15 Accepted 110ms 17.773 MiB
#16 Accepted 116ms 17.938 MiB
#17 Accepted 167ms 18.461 MiB
#18 Accepted 117ms 17.711 MiB
#19 Accepted 124ms 17.906 MiB
#20 Accepted 127ms 17.91 MiB
#21 Accepted 126ms 17.879 MiB
#22 Accepted 127ms 17.977 MiB
#23 Accepted 130ms 17.871 MiB
#24 Accepted 124ms 17.938 MiB
#25 Accepted 117ms 17.93 MiB
#26 Accepted 122ms 17.785 MiB
#27 Accepted 116ms 17.766 MiB
#28 Accepted 120ms 17.84 MiB
#29 Accepted 122ms 17.891 MiB
#30 Accepted 123ms 18.238 MiB
#31 Accepted 124ms 18.461 MiB
#32 Accepted 111ms 17.789 MiB
#33 Accepted 119ms 18.352 MiB
#34 Accepted 123ms 17.844 MiB
#35 Accepted 177ms 18.461 MiB

Code

/*For today, you happen to be the defeated. But what will you become tomorrow?*/

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

#define dbg if(debugg)
#define F first 
#define S second 
#define int long long
bool debugg = false;

template <typename T>
using order_set = tree<T, null_type,less<T>, rb_tree_tag,tree_order_statistics_node_update>;

template <typename T>
using minheap = priority_queue<T, vector<T>, greater<T>>;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());  

const int N = 100005;
vector<int>divisors[N];
void sieve()
{
    for(int i = 1; i < N; i ++){
        for(int j = i; j < N; j += i){
            divisors[j].push_back(i);
        }
    }
}
int cnt[N], tot[N];
void solve()
{
    
    int n;
    cin >> n;
    vector<int>v(n);
    int gd = 0;
    memset(cnt, 0, sizeof(cnt));
    memset(tot, 0, sizeof(tot));
    for(int i = 0; i < n; i ++){
        cin >> v[i];
        gd = __gcd(gd, v[i]);
        cnt[v[i]] += 1;
    }

    for(int i = 1; i < N; i ++){
        for(int j = i; j < N; j += i){
            tot[i] += cnt[j];
        }
    }
    int ans = 2 * gd;
	assert(n > 0);
    for(int itr = 0; itr < 10; itr ++){
        int x = v[rng() % n], y = v[rng() % n];
        for(int i : divisors[x]){
            for(int j : divisors[y]){
                
                if(i == j) continue;
                int lm = (1ll * i * j) / gcd(i, j);
                if(lm >= N) lm = 0;
				assert(lm < N);
                if(tot[i] + tot[j] - tot[lm] != n) continue;
                int p = tot[i], q = tot[j];
                if(max(p, q) >= ((n + 1) / 2)){
                    if(min(p, q) >= (n / 2)){
                        ans = max(ans, i + j);
                    }
                }
                
            }
        }
    }

    cout << ans << '\n';
}



int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int t  = 1;
    cin>>t;

    sieve();

    while(t--){

        solve();

    }

    return 0;

}

Information

Submit By
Type
Submission
Problem
P1077 Even Odd GCD (Hard Version)
Language
C++20 (G++ 13.2.0)
Submit At
2024-08-17 05:59:52
Judged At
2024-10-03 13:18:52
Judged By
Score
100
Total Time
177ms
Peak Memory
18.461 MiB