/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 85ms 16.156 MiB
#2 Accepted 95ms 16.129 MiB
#3 Accepted 92ms 16.164 MiB
#4 Accepted 96ms 16.336 MiB
#5 Accepted 96ms 16.199 MiB
#6 Accepted 99ms 16.332 MiB
#7 Accepted 104ms 16.328 MiB
#8 Accepted 100ms 16.316 MiB
#9 Accepted 99ms 16.172 MiB
#10 Accepted 102ms 16.32 MiB
#11 Accepted 98ms 16.336 MiB
#12 Accepted 99ms 16.23 MiB
#13 Accepted 101ms 16.41 MiB
#14 Accepted 96ms 16.082 MiB
#15 Accepted 124ms 16.562 MiB
#16 Accepted 128ms 16.641 MiB
#17 Accepted 270ms 17.168 MiB
#18 Accepted 138ms 16.262 MiB
#19 Accepted 207ms 16.453 MiB
#20 Accepted 200ms 16.469 MiB
#21 Accepted 190ms 16.488 MiB
#22 Accepted 198ms 16.492 MiB
#23 Accepted 202ms 16.496 MiB
#24 Accepted 255ms 16.52 MiB
#25 Accepted 157ms 16.254 MiB
#26 Accepted 196ms 16.328 MiB
#27 Accepted 448ms 16.504 MiB
#28 Accepted 171ms 16.551 MiB
#29 Accepted 240ms 16.539 MiB
#30 Accepted 547ms 17.078 MiB
#31 Accepted 506ms 17.086 MiB
#32 Accepted 140ms 16.473 MiB
#33 Accepted 115ms 17.68 MiB
#34 Accepted 129ms 16.359 MiB
#35 Accepted 1053ms 17.078 MiB

Code

#pragma GCC optimize("O3,unroll-loops,Ofast")
// #pragma GCC target("avx2")
#include<bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
#define int long long
#define endl '\n'

using namespace std;
using pii = pair<int, int>;
using tup = tuple<int, int, int>;

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// template <class T> using ordered_set = tree<T, null_type,
//                          less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const int inf = (1e15)+5;
const int mod = 1000000007;
const double eps = 1e-6;
const int N = 100001;

vector<int> divs[N];
void preprocess() {
	for (int i = 1; i < N; i++) {
		for (int j = i; j < N; j += i) {
			divs[j].push_back(i);
		}
	}
}

int n, a[N];
int cnt[N];


int calc(int x) {
	int tot = 0, out = 0;
	for(int i=1; i<=n; i++) {
		if(a[i] % x == 0) tot++;
		else out = gcd(out, a[i]);
	}

	int onno = n - tot;
	int lage;

	if(n % 2 == 0) {
		if(tot < n/2) return 0;
		lage = n / 2;
	}

	else {
		if(tot >= n/2+1) lage = n/2;
		else if(tot == n/2) lage = n/2+1;
		else return 0;
	}

	lage -= onno;

	for(int i=1; i<=n; i++) {
		if(a[i] % x) continue;
		for(int j : divs[a[i]])
			cnt[j]++;
	}

	// cout << tot << ' ' << onno << ' ' << lage << ' ' << out << endl;
	int ret = 0;
	for(int i=1; i<N; i++) {
		if(out % i or cnt[i] < lage) continue;
		ret = max(ret, i);
	}

	for(int i=1; i<=n; i++) {
		if(a[i] % x) continue;
		for(int j : divs[a[i]])
			cnt[j]--;
	}
	// if(out % x == 0) ret *= x;
	
	// cout << x << ": " << ret + x << endl;
	return ret + x;
}

void solve(int tc) {
	cin >> n;
	for(int i=1; i<=n; i++) cin >> a[i];

	bool f = 1;
	for(int i=2; i<=n; i++) f &= (a[i] == a[i-1]);
	if(f) {
		cout << 2 * a[1] << endl;
		return;
	}

	int who = a[1];
	for(int i=2; i<=n; i++) {
		if(divs[a[i]].size() < divs[who].size())
			who = a[i];
	}
	int ans = 0;
	for(int i : divs[who]) ans = max(ans, calc(i));

	cout << ans << endl;
}
    
int32_t main() {
    cin.tie(NULL)->sync_with_stdio(false);
    cout.precision(10);

    preprocess();

    int T = 1;
    cin >> T;

    for (int i = 1; i <= T; i++) {
        solve(i);
    }

    return 0;
}

Information

Submit By
Type
Submission
Problem
P1077 Even Odd GCD (Hard Version)
Contest
Bangladesh 2.0
Language
C++17 (G++ 13.2.0)
Submit At
2024-08-16 17:18:54
Judged At
2024-11-11 03:12:03
Judged By
Score
100
Total Time
1053ms
Peak Memory
17.68 MiB