Количество не взаимно простых пар из диапазона [1, arr[i]] для каждого элемента массива

Дан массив arr[] , состоящий из N целых чисел, задача для каждого i ^-го элемента массива состоит в том, чтобы найти количество не взаимно простых пар из диапазона [1, arr[i]] .

Примеры:

Input: N = 2, arr[] = {3, 4}
Output: 2 4
Explanation:

1. All non-co-prime pairs from the range [1, 3] are (2, 2) and (3, 3).
2. All non-co-prime pairs from the range [1, 4] are (2, 2), (2, 4), (3, 3) and (4, 4).

Input: N = 3, arr[] = {5, 10, 20}
Output: 5 23 82

Наивный подход: самый простой подход к решению проблемы состоит в том, чтобы перебрать каждый i ^-й элемент массива, а затем сгенерировать каждую возможную пару из диапазона [1, arr[i]] и для каждой пары проверить, является ли она несовместной. -простой, т.е. НОД пары больше 1 или нет.

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

• Переберите диапазон [0, N – 1] , используя переменную, скажем , i, и выполните следующие шаги:
  • Инициализируйте переменные lastEle как arr[i] и count как 0 , чтобы сохранить последнее значение текущего диапазона и количество взаимно простых пар соответственно.
  • Перебрать каждую пару из диапазона [1, arr[i]], используя переменные x и y , и сделать следующее :
    • Если GCD(x, y) больше 1 , то приращение увеличивается на 1 .
  • Наконец, напечатайте количество в качестве ответа.

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

Временная сложность: O(N*M ² *log(M)), где M — максимальный элемент множество.
Вспомогательное пространство: O(1)

Эффективный подход. Описанный выше подход можно оптимизировать с помощью функции totient Эйлера и массива сумм префиксов. Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте два массива, скажем, phi[] и ans[] как 0 , где i ^-й элемент массива представляет количество целых чисел, взаимно простых с i , и количество не взаимно простых пар, образованных из диапазона [1, arr[i]].
• Переберите диапазон [1, MAX], используя переменную, скажем , i, и присвойте i значению phi[i].
• Переберите диапазон [2, MAX], используя переменную, скажем , i, и выполните следующие шаги:
  • Если phi[i] = i, то выполните итерацию по диапазону [i, MAX], используя переменную j , и выполните следующие шаги:
    • Уменьшите phi[j] / i от phi[j] и затем увеличьте j на i .
• Переберите диапазон [1, MAX], используя переменную, скажем , i, и выполните следующие шаги:
  • Обновите ans[i] до ans[i – 1] + (i – phi[i]).
• Наконец, после выполнения вышеуказанных шагов напечатайте массив ans[] .

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

Временная сложность: O(N+ M*log(N)), где M — максимальный элемент массива.
Вспомогательное пространство: O(M+N)