Формулка скорее всего. Попробуй найти закономерность

Там есть закономерность.Я использовал длинку с бинпоиском.

Здесь можно найти информацию об этой последовательности.

Последовательность выглядит так:

a[0] = 0
if (a[id - 1] is square) a[id] = a[id - 1] + 1  
else a[id] = a[id - 1] + 2  

Очевидно, что ответ это (2 * N — S), где S — количество квадратов до a[N].
S = X + 1, где X = максимальное X что X² <  = a[N]

Надо найти X, делаем это бинпоиском.
Допустим у нас какое то X, хотим проверить X^2 <= a[N].
Если X подходит то X-1 тоже подходит, значит у нас ответ для X-1 это 2*N-(X-1)+1 (делаем + поскольку S=X-1+1).

X^2 <= 2*N-X
X^2+X <= 2*N
X(X+1) <= 2*N

Код маленький, если не учитывать длинную арифметику.

P.S. Было бы неплохо, если бы в редактировании был предпросмотр.