Учитывая большое N, мне нужно перебрать все фи (k) так, чтобы 1 <k <N быстро, то есть O(N logN)
сложность времени.
Поскольку значения N будут около 10 12 важно, чтобы сложность памяти составляла суб O(N)
.
Является ли это возможным? Если так, то как?