PROBLEM LINK
Author: Harsh Shah
Tester: Dhrub Kumar
Editorialist: Harsh Shah
DIFFICULTY:
Easy
PREREQUISITES:
Implementation, maths , Harmonic Lemma.
PROBLEM:
Rohit wants to drink bournvita which is defined by an array of N positive integers. But Rohit wants it to be magical.Magic Strength of bournvita is inversely proportional to the size of array. To make it magical Jaadu uses special magic called dhuuuuuupp. He can use atmost K such moves ,where K = 2.
In one move he can choose the i^{th} element and remove all such elements j such that a_j is divisible by a_i. In the end he also removes the i^{th} element.
After using some operations , help Jaadu to make the bournvita as magical as possible.
EXPLANATION:
The solution to this problem is very straightforward to understand. As N \leq 3000 . One can simply check all pairs of element and remove the pairs with largest divisor set size. Therefore we can calculate the total set size as :
totalsize = set_i + set_j - set(lcm_{i,j})
Thus the only task left is to compute the size of sets of all numbers till 1e6 efficiently. This can be done using modified sieve , where for each i , { 1 \leq i \leq 1e6 } iterate over all multiples of i and add to size of set_i . Therefore the overall time complexity of the solution would be
O(a\log{a} + n^2) , where a = 1e6.
SOLUTION
Setter's Solution
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 1;
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, answer = 0; cin >> n;
vector<int>a(n), numberOfMultiples(N);
for(auto &i : a) cin >> i;
for(auto &i : a) numberOfMultiples[i]++;
for(int i = 1; i < N; i++)
{
for(int j = 2 * i; j < N; j += i)
{
numberOfMultiples[i] += numberOfMultiples[j];
}
}
for(int i = 0; i < n; i++)
{
for(int j = i; j < n; j++)
{
int LCM = (a[i] * a[j]) / __gcd(a[i], a[j]);
int commonSetSize = (LCM >= N ? 0 : numberOfMultiples[LCM]);
answer = max(answer, numberOfMultiples[a[i]] + numberOfMultiples[a[j]] - commonSetSize);
}
}
cout << n - answer << "\n";
}