PROBLEM LINK: Click here
Contest: Hey Newbees, Here is Some Honey -ROUND 3
Author: Arefin Labib
Co-Author: Samia Rahman
Tester: Redowan Ibrahim
Tester: Sanjida Akter
Tester: Nazmus Sakib
DIFFICULTY:
Medium
PREREQUISITES:
Prime factorization, LCM
PROBLEM:
You are given an array of integers A. You have to construct an array B such that B_i is the number of non prime divisors of A_i. Now you have to find out a pair of integer A_i and A_j such that LCM(B_i , B_j) is the maximum than any other pair in that array.
N.B. if two pair have the same LCM, the pair which have the maximum value among them will get priority. Suppose there is another pair (A_p,A_q) and LCM(B_p,B_q)=LCM(B_i,B_j)=maxLCM in the array. then-
- if max(A_i,A_j)>max(A_p,A_q) then (A_i,A_j) will be the SCI.
- if max(A_i,A_j)=max(A_p,A_q) then, if min(A_i,A_j)>min(A_p,A_q) then (A_i,A_j) will be the SCI.
EXPLANATION:
Solution of this problem is straightforward. You have to factorize all the number of the array and find the non prime divisors and store in array B. Then you have to find the maximum possible LCM(B_i,B_j) and print (A_i,A_j).
If we observe the question, we can see that, though numbers of the arrays can be quite lerge ( \leq 10^{12}) but the constraints are very small and there are enough time. So we dont need to pre calculate anything. Just factorize each number in an efficient way( you can see the factorize function in the solve given below), calculate and store the number of non-prime divisors in an array with it’s corresponding number. You can take a vector pair. Then sort the pair so that it is sorted in descending order giving first priority to the non prime divisors and then the original number. Now iterate over the non prime divisors, calculate LCM and find which is maximum.
You have to print the max(A_i,A_j) first and then min(A_i,A_j).
TIME COMPLEXITY
O(n^{2})
SOLUTIONS:
C++
//BISMILLAHIR RAHMANIR RAHIM
//INNALLAHA_MA_AS_SABIRIN
//SOTO's
#include<bits/stdc++.h>
#define ll long long
#define ls \
ios_base::sync_with_stdio(false); \
cin.tie(0);
#define __ <<" "<<
#define loop(m,n) for(m=0;m<n;m++)
#define rloop(m,n) for(m=n-1;m>=0;m--)
#define itr ::iterator
#define itloop(ds) for(it=ds.begin();it!=ds.end();it++)
#define case(z) "Case " << z++ << ": "
#define test_inp() ll Tc,l=1;cin>>Tc;while(Tc--)
#define sf(T) scanf("%lld",&T)
#define pf(T) printf("%lld\n",T)
#define ptf(b) puts(b?"Yes":"No")
#define newline cout<<endl
#define quit return 0
using namespace std;
map<ll,ll>mp;
bool cmp(pair<ll,ll>i1,pair<ll,ll>i2)
{
if(i1.first == i2.first)
{
return (i1.second> i2.second);
}
else
{
return (i1.first >i2.first);
}
}
void factorize(long long n)
{
mp.clear();
int count = 0;
while ((n % 2)!=1) {
n>>=1;
count++;
}
if (count!=0)
mp[2]=count;
for (long long i = 3; i <= sqrt(n); i += 2) {
count = 0;
while (n % i == 0) {
count++;
n = n / i;
}
if (count!=0)
mp[i]=count;
}
if (n > 2)
mp[n]=1;
}
int main()
{
//freopen("ain.txt","r",stdin);
//freopen("aoutt.txt","w",stdout);
test_inp(){
ll n;
cin>>n;
ll i,p;
vector<pair<ll,ll> >v;
loop(i,n)
{
cin>>p;
ll s=1;
factorize(p);
map<ll,ll>::iterator it;
for(it=mp.begin();it!=mp.end();it++)
{
s*=((it->second)+1);
}
v.push_back(make_pair(s-mp.size(),p));
}
sort(v.begin(),v.end(),cmp);
ll mx=0,lcm,j,sci_1,sci_2;
loop(i,n)
{
if((v[i].first)*(v[i].first)<mx)
break;
for(j=i+1;j<n;j++)
{
lcm=((v[i].first*v[j].first)/(__gcd(v[i].first,v[j].first)));
if(mx<lcm)
{
mx=lcm;
sci_1=v[i].second;
sci_2=v[j].second;
}
}
}
cout << max(sci_1,sci_2) __ min(sci_1,sci_2) << endl;
}
quit;
}