Найдите множество размера K такое, что любое значение множества взаимно просто с любым элементом массива.

Опубликовано: 25 Февраля, 2023

Дан набор S , состоящий из чисел 1, 2, 3, . . ., N и целое число K , задача состоит в том, чтобы сформировать множество A , взяв K значений из S так, чтобы любая пара, образованная путем взятия одного значения из S и другого из A, всегда была взаимно простой. (Два числа взаимно просты, если их НОД равен 1).

Примечание. Если существует несколько решений, выведите любое из них, а если такого набора не существует, выведите -1.

Примеры:

Input: N = 4, K = 1
Output: 1

Explanation: We can choose [1] for set A and remaining numbers 
[2, 3, 4] contained in set S. 1 is coprime with 2, 3 and 4 so the condition is satisfied.

Input: N = 4, K = 2
Output: 1 3

Подход: Задача может быть решена на основе следующего наблюдения:

Let’s focus on prime numbers since the gcd function works on primes independently of other primes.

  • Consider all primes p such that p ∗ 2 ≤ N. Hence, 2 and p must be in same component for all primes ≤ N / 2. Let’s add this to a set called X.
  • All non-prime integers shall also lie in the same set as their prime factors. So any integer > 1 which is not a prime shall also be added to this X.

We can claim that the elements present in X shall all be in either S or A.

  • For example, for S = 13, the primes less than 6.5 are 2, 3, 5, so the set S formed is [2, 3, 4, 5, 6, 8, 9, 10, 12]. Elements not present in this set are 1 and all primes greater than N/2. Let’s say there are C such elements. For N = 13, we have [1, 7, 11, 13]. C = 4 here.
  • So, if we can add elements from [1, 7, 11, 13] to make a set of size K or size N − K, then it is possible to find such S and A.
  • It is only when we have either K ≤ C or K ≥ N−C that we can form set S and A. 

The list of primes can be computed using the sieve of Eratosthenes.

Следуйте шагам, указанным ниже, чтобы реализовать идею:

  • Найдите простые числа в указанном выше диапазоне.
  • Теперь проверьте значение C и NC.
  • Сравните это с K согласно упомянутым условиям.
  • Если условия выполнены, то формируем множества, иначе такое множество невозможно.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N * log(log(N)))
Вспомогательное пространство: O(1)

РЕКОМЕНДУЕМЫЕ СТАТЬИ