Подсчитайте различные пары индексов в массиве, у которых GCD и LCM совпадают

Для заданного массива A[] длины N задача состоит в том, чтобы найти общее количество различных пар (i, j) индексов, где 1 ≤ i < j ≤ N , таких, что наибольший общий делитель(gcd) и наименьшее общее кратное( lcm) этих элементов равны.

Примеры:

Input: A[] = {2, 5, 5, 5, 6} 
Output: 3 

Explanation: Here pair (i, j) are: (2, 3), (3, 4), and (2, 4). 
To elaborate, gcd(A₂, A₃) = lcm(A₂, A₃) = 5.

Input: A[] = {22, 22, 38, 38} 
Output: 2

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

Наблюдения:

• The observation to be made here is as follows: gcd(A_i, A_j) = lcm(A_i, A_j)⟺ A_i = A_j
• So, the problem reduces to simply counting the number of pairs of equal elements in A.
• Build a frequency map of the elements of A (using map/unordered_map in C++, TreeMap/Hashmap in Java, or dict in python) and then iterate across its elements.
• If an element x has a frequency of f_x, then it contributes f_x⋅(f_x−1)/2 pairs to the answer, so sum this value across all x.

Выполните следующие шаги, чтобы решить проблему:

• Объявите хэш-карту.
• Начните перебирать весь массив
  • Если элемент присутствует на карте, то увеличьте значение частоты на 1.
  • В противном случае вставьте этот элемент в карту.
• После этого начните обход карты и получите значение (частоту элемента).
• Если элемент x имеет частоту f _x , то он вносит f _x ⋅ (f _x − 1) / 2 пары в ответ, поэтому суммируйте это значение по всем x.

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

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