Количество различных целых чисел, принадлежащих первым N терминам по крайней мере одного из заданных GP
Учитывая две геометрические прогрессии (a1, r1) и (a2, r2), где (x, y) представляет GP с начальным термином x и знаменателем y и целым числом N , задача состоит в том, чтобы найти количество различных целых чисел, которые принадлежат первые N членов хотя бы одной из заданных геометрических прогрессий.
Примеры:
Input: N = 5, a1 = 3, r1 = 2, a2 = 6, r2 = 2
Output: 6
Explanation: The first 5 terms of the given geometric progressions are {3, 6, 12, 24, 48} and {6, 12, 24, 48, 96} respectively. Hence, the total count of distinct integers in the GP is 6.Input: N = 5, a1 = 3, r1 = 2, a2 = 2, r2 = 3
Output: 9
Explanation: The first 5 terms of the given geometric progressions are {3, 6, 12, 24, 48} and {2, 6, 18, 54, 162} respectively. Hence, the total count of distinct integers in the GP is 9.
Подход: Данную проблему можно решить, заметив, что общее количество различных целых чисел можно рассчитать, создав первые N членов обеих геометрических прогрессий и удалив повторяющиеся члены. Это может быть достигнуто за счет использования заданной структуры данных. Во-первых, сгенерируйте все N терминов 1 -й ВП и вставьте их в набор S . Аналогично вставляем в множество S термы 2- й ГП. Размер множества S и есть требуемый ответ.
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O (N * log N)
Вспомогательное пространство: O(N)