PROBLEM LINK:
Author: lightspeed11
Tester: Jay_1048576
Editorialist: still_me
DIFFICULTY:
EASY
PREREQUISITES:
Sieve , Constructive or Randomized algorithm
PROBLEM:
Given an array of size N, find the largest element that divides \lfloor N/2 \rfloor elements.
QUICK EXPLANATION:
We can find all the factors of a number X with its prime factors less than \sqrt X only. There are around 3500 prime numbers under 10^{9/2}, so we need at most around 4500 (number of primes numbers under 10^9 + number of factors) operations to factorize any number till 10^9. So to factorize 5*10^4 numbers it will take order of 10^8 operations, which can be implemented well within 5 second limit.
EXPLANATION:
The Brute Force solution can be used to factorize each number and store frequency of each factors for every the number in the array. The complexity of this approach would be O(N* \sqrt max(a_i ) ) ~ 10^9 operations for given constraints. We need to optimize this approach by a factor of 10.
This can be done using 2 properties:
1. Upper bound of the number of factors of an integer X is around X^{1/3}.
2. Number of primes less than a given number X is approximately X/ln(x).
We precompute all the prime numbers less than 10^{9/2} and compute factors of any number till 10^9.
Due to the above two properties we reduce the the time complexity by a factor of 10.
ALTERNATE SOLUTION:
If we randomly select a number from the array there is a 1/2 probability that this number will be in the optimum subsequence (Sherlock’s subsequence).
We select a random number we can factorize this number in \sqrt a_i operations. Then we iterate through entire array and count the frequency of each factor dividing any number in the array. The GCD would be the largest number with frequency at least \lfloor N/2 \rfloor .
We can do this operation once in N* \sqrt a_i operations, and the probability of this answer being correct would be 1/2. If we repeat this process 30 times and store the maximum of all of them, we get the correct answer with a probability of 1-2^{-30}.
SOLUTIONS:
Setter's Solution
// RANDOMIZED SOLUTION
#include<bits/stdc++.h>
#define ll long long int
#define fab(a,b,i) for(int i=a;i<b;i++)
#define pb push_back
#define db double
#define mp make_pair
//#define endl "\n"
#define f first
#define se second
#define all(x) x.begin(),x.end()
#define vll vector<ll>
#define vi vector<int>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define quick ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
using namespace std;
const int MOD = 1e9 + 7;
ll add(ll x, ll y) {ll res = x + y; return (res >= MOD ? res - MOD : res);}
ll mul(ll x, ll y) {ll res = x * y; return (res >= MOD ? res % MOD : res);}
ll sub(ll x, ll y) {ll res = x - y; return (res < 0 ? res + MOD : res);}
ll power(ll x, ll y) {ll res = 1; x %= MOD; while (y) {if (y & 1)res = mul(res, x); y >>= 1; x = mul(x, x);} return res;}
ll mod_inv(ll x) {return power(x, MOD - 2);}
ll lcm(ll x, ll y) { ll res = x / __gcd(x, y); return (res * y);}
int main()
{
quick;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#ifndef ONLINE_JUDGE
freopen("1st.in", "r", stdin);
freopen("1st.out", "w", stdout);
#endif
int t = 1;
cin >> t;
while (t--)
{
int n;
cin >> n;
vector<int> a(n);
fab(0, n, i)
{
cin >> a[i];
}
int req = n / 2;
int ans = 1;
auto getFact = [&](int n)->vector<int> {
vector<int> a = {n};
for (int i = 2; i * i <= n; i++)
{
if (n % i == 0)
{
a.pb(i);
if (n / i != i)
{
a.pb(n / i);
}
}
}
return a;
};
map<int,int> vis;
map<int,int> checked;
fab(0, 30, i)
{
int p = uniform_int_distribution<int> (0, n - 1)(rng);
if(vis[a[p]])
continue;
vis[a[p]]=1;
vector<int> b = getFact(a[p]);
for (int &x : b)
{
int cnt = 0;
if(checked.find(x)!=checked.end())
continue;
checked[x]++;
fab(0, n, j)
{
cnt += ((a[j] % x) == 0);
}
if (cnt >= req)
ans = max(ans, x);
}
}
cout << ans << endl;
}
cerr << "time taken : " << (float)clock() / CLOCKS_PER_SEC << " secs" << endl;
return 0;
}
Tester's Solution
/*...................................................................*
*............___..................___.....____...______......___....*
*.../|....../...\........./|...../...\...|.............|..../...\...*
*../.|...../.....\......./.|....|.....|..|.............|.../........*
*....|....|.......|...../..|....|.....|..|............/...|.........*
*....|....|.......|..../...|.....\___/...|___......../....|..___....*
*....|....|.......|.../....|...../...\.......\....../.....|./...\...*
*....|....|.......|../_____|__..|.....|.......|..../......|/.....\..*
*....|.....\...../.........|....|.....|.......|.../........\...../..*
*..__|__....\___/..........|.....\___/...\___/.../..........\___/...*
*...................................................................*
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 50005;
bool sieve[N];
vector<int> primes,factors;
vector<pair<int,int> > pf[N];
map<int,int> m;
void computeFactors(vector<pair<int,int> > &pf)
{
for(int i=0;i<pf.size();i++)
{
int n = factors.size();
for(int j=0;j<n;j++)
{
int p=pf[i].first;
for(int k=1;k<=pf[i].second;k++)
{
factors.push_back(factors[j]*p);
p=p*pf[i].first;
}
}
}
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
memset(sieve,true,sizeof(sieve));
sieve[1]=false;
for(int i=2;i*i<N;i++)
{
if(sieve[i])
{
primes.push_back(i);
for(int j=i*i;j<N;j+=i)
sieve[j]=false;
}
}
int tt=1;
cin >> tt;
while(tt--)
{
int n;
cin >> n;
int a[n];
for(int i=0;i<n;i++)
cin >> a[i];
for(int i=0;i<n;i++)
pf[i].clear();
for(int i=0;i<primes.size();i++)
{
for(int j=0;j<n;j++)
{
int c=0;
while(a[j]%primes[i]==0)
{
a[j]/=primes[i];
c++;
}
if(c>0)
pf[j].push_back({primes[i],c});
}
}
for(int i=0;i<n;i++)
{
if(a[i]!=1)
pf[i].push_back({a[i],1});
}
m.clear();
for(int i=0;i<n;i++)
{
factors.clear();
factors.push_back(1);
computeFactors(pf[i]);
for(int i=0;i<factors.size();i++)
{
m[factors[i]]++;
}
}
int ans=1;
for(auto it=m.begin();it!=m.end();it++)
{
if(it->second>=n/2)
ans=it->first;
}
cout << ans << '\n';
}
return 0;
}
Editorialist's Solution
#include <bits/stdc++.h>
#define endl "\n"
#define quick \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define map unordered_map
using namespace std;
void generate(vector<pair<int, int>> &b, int j, int a, map<int, int> &c)
{
int n = b.size();
if (j == n)
{
c[a]++;
return;
}
for (int i = 0; i <= b[j].second; i++)
generate(b, j + 1, a * pow(b[j].first, i), c);
return;
}
void factorize(int a, map<int, int> &b, vector<int> &primes)
{
map<int, int> x;
int c = a;
for (int i = 0; primes[i] * primes[i] <= a; i++)
{
while (c % primes[i] == 0)
{
x[primes[i]]++;
c /= primes[i];
}
}
if (c > 1)
x[c]++;
vector<pair<int, int>> xx;
for (auto i : x)
xx.push_back(i);
generate(xx, 0, 1, b);
}
signed main()
{
quick;
int N = 5e4;
vector<char> is_prime(N + 1, true);
is_prime[0] = is_prime[1] = false;
for (int i = 2; i <= N; i++)
{
if (is_prime[i] && (long long)i * i <= N)
{
for (int j = i * i; j <= N; j += i)
is_prime[j] = false;
}
}
vector<int> primes;
for (int i = 2; i <= N; i++)
{
if (is_prime[i])
primes.push_back(i);
}
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
vector<int> a(n);
for (int &i : a)
{
cin >> i;
}
map<int, int> b;
for (int i : a)
factorize(i, b, primes);
int mx = 1;
for (auto i : b)
if (i.second >= n / 2)
mx = max(mx, i.first);
cout << mx << endl;
}
return 0;
}