PROBLEM LINK: The Chosen One
Setter: Abhishek Jugdar
Tester: Aman Singhal
Editorialist: Abhishek Jugdar
DIFFICULTY:
MEDIUM
PREREQUISITES:
Sieve, Principle of Inclusion-Exclusion
PROBLEM:
Given N numbers, A1, A2, A3..., AN ranging from 1 to N, find the Kth smallest GCD and print any pair of indices with the given GCD.
EXPLANATION:
We can modify sieve to compute res[i] = no. of pairs having GCD = i.
Compute freq[ ] = frequency of elements in the array beforehand.
for(i = n; i > 0; i–) {
x = \sum_{j | i}^{N} freq[j]
res[i] = \frac{x*(x-1)}{2} - \sum_{j | i}^{N} res[j];
}
Let g = Kth smallest GCD
For finding any pair having GCD = g, find all numbers x divisible by g, divide them by g, thus reducing the problem to finding a co-prime pair in this new array. One of the ways is: For each number x in the new array, find if there is a number which is not divisible by any of the prime factors of x(can be done using inclusion-exclusion, pre-compute prime factors using another sieve), if there is such a number, say x, we can set x as the first number and iterate back to find the second number, say y.
Time Complexity - nlog(n) + n*(2^x)*x
Here x denotes maximum number of distinct prime factors in any number from 1 to 10^6, which is 7. But with appropriate checks it works much faster in practice. You can refer to the solutions below for implementation details.
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
int t;
cin >> t;
while (t--)
{
int n;
long long k;
cin >> n >> k;
vector <int> arr(n);
for (int &x : arr)
cin >> x;
vector <int> cnt(n + 1, 0); // freq count
vector <long long> res(n + 1, 0);
for (int x : arr)
cnt[x]++;
for (int i = n; i > 0; i--) {
int div_count = 0;
long long rem = 0;
for (int j = i; j <= n; j += i) {
div_count += cnt[j];
rem += res[j];
}
res[i] = (1LL * div_count * (div_count - 1)) / 2 - rem;
}
int ans = 0;
for (int i = 1; i <= n; i++) {
if (k <= res[i]) {
ans = i;
break;
}
k -= res[i];
}
cout << ans << '\n';
// Part to find two indices having k-th gcd.
vector <int> spf(n + 1, 0); // smallest prime factor
cnt.assign(n + 1, 0);
for (int i = 2; i <= n; i++) {
if (!spf[i]) {
spf[i] = i;
if (n / i < i) continue;
for (int j = i * i; j <= n; j += i) {
if (!spf[j])
spf[j] = i;
}
}
}
vector <pair <int, int> > req;
map <int, int> same_cnt; // Only 1 duplicate for each number is needed, rest copies can be discarded
for (int i = 0; i < n; i++) {
if (arr[i] % ans == 0) {
if (same_cnt[arr[i]] > 1) continue;
same_cnt[arr[i]]++;
req.push_back(make_pair(arr[i] / ans, i));
}
}
int first_index, second_index;
// Now we have to search for a number such that atleast one number before it isn't divisible by any prime factors of our number.
int first_num = -1;
for (int i = 0; i < req.size(); i++) {
int x = req[i].first;
vector <int> primes;
while (x > 1) {
int small = spf[x];
primes.push_back(small);
while (x % small == 0)
x /= small;
}
int sz = primes.size();
int div_count = 0;
for (int j = 1; j < (1 << sz); j++) {
int curr_number = 1;
for (int l = 0; l < sz; l++) {
if (j >> l & 1)
curr_number *= primes[l];
}
int bits = __builtin_popcount(j);
div_count += (bits & 1 ? cnt[curr_number] : -cnt[curr_number]);
cnt[curr_number]++;
}
if (div_count < i) {
first_num = i;
break;
}
}
assert(first_num != -1);
first_index = req[first_num].second;
for (int i = first_num - 1; i >= 0; i--) {
if (__gcd(req[first_num].first, req[i].first) == 1) {
second_index = req[i].second;
break;
}
}
int curr_gcd = __gcd(arr[first_index], arr[second_index]);
assert(ans == curr_gcd);
cout << first_index + 1 << ' ' << second_index + 1 << '\n';
}
}
Tester's Solution (Python)
import sys,collections
import math as mt
input=sys.stdin.readline
MAXN = 1000001
spf = [0 for i in range(MAXN)]
#sieve for storing prime numbers
def sieve():
spf[1] = 1
for i in range(2, MAXN):
spf[i] = i
for i in range(4, MAXN, 2):
spf[i] = 2
for i in range(3, mt.ceil(mt.sqrt(MAXN))):
if (spf[i] == i):
for j in range(i * i, MAXN, i):
if (spf[j] == j):
spf[j] = i
sieve()
#For getting factorization of numbers
def getFactorization(x):
ret = list()
while (x != 1):
ret.append(spf[x])
x = x // spf[x]
return ret
def bitsoncount(x):
return bin(x).count('1')
#function to find any coprime pair in an array
def coprimepair(C):
high=max(C)
n=len(C)
count= [0 for i in range(high+1)]
for i in range(0,n):
count[C[i]]=count[C[i]]+1
cal= [0 for i in range(high+1)]
for i in range(high,1,-1):
counter=0
j=i
while(j<=high):
counter=counter+count[j]
j=j+i
cal[i]=counter
v1=0
ind=0
for i in range(n):
PA=getFactorization(C[i])
PA=list(set(PA))
m=len(PA)
odd=0
even=0
ps=1<<m
for counter in range(1,ps):
p=1
for j in range(m):
if (counter & (1<<j)):
p*=PA[j]
if (bitsoncount(counter) & 1):
odd+=cal[p]
else:
even+=cal[p]
if ((odd-even)!=n):
v1=C[i]
ind=i
break
v2=0
for i in range(n):
if (ind!=i and mt.gcd(v1,C[i])==1):
v2=C[i]
break
return v1,v2
#print(getFactorization(24))
def kgcd(n,A,K):
high=max(A)
count = [0 for i in range(high+1)]
for i in range(0, n) :
count[A[i]]=count[A[i]]+1
counter=0
ans=0
vis=[0 for i in range(high+1)] #vis to avoid multiple count of same values
for i in range(high,0,-1):
j=i
rv=0
while(j<=high):
counter=counter+count[j]
rv=rv+vis[j]
j=j+i
n1=(counter*(counter-1))//2
ans=ans+n1-rv
vis[i]=n1-rv
if (ans>=K):
return i
counter=0
return 1
def main():
T=int(input())
for _ in range(T):
N,K=map(int,input().split())
A=list(map(int,input().split()))
val=(N*(N-1))//2
ans=kgcd(N,A,val-K+1)
print(ans)
G={}
for i in range(N+1):
G[i]=0
C=[]
for i in range(N):
if (A[i]%ans==0 and G[A[i]//ans]<=2 ):
G[A[i]//ans]=G[A[i]//ans]+1
C.append(A[i]//ans)
v1,v2=coprimepair(C)
v1,v2=v1*ans,v2*ans
#print(v1,v2)
ind1,ind2=-1,-1
for i in range(N):
if (A[i]==v1):
ind1=i+1
break
for i in range(N):
if (i!=(ind1-1) and A[i]==v2):
ind2=i+1
break
print(ind1,ind2)
main()
For doubts, please leave them in the comment section, I’ll address them.