Найти количество пар натуральных чисел, удовлетворяющих неравенству

Question

Я пытаюсь решить проблему программирования, в которой мне нужно отобразить число положительных целых решений неравенства x² + y² < n, где n задано пользователем.Я уже написал код, который, кажется, работает, но не так быстро, как хотелось бы.Есть ли способ ускорить его?Мой текущий код:

#include <iostream>
#include <cmath>
using namespace std;
int main()
{
    long long n, i, r, k, p, a;
    cin >> k;
    while (k--)
    {
        r = 0;
        cin >> n;
        p = sqrt(n);
        for (i = 1; i <= p; i++)
        {
            a = sqrt(n - (i * i));
            r += a;
            if ((((i * i) + (a * a)) == n) && (a > 0))
            {
                r--;
            }
        }
        cout << r << "\n";
    }
    return 0;
}

Редактировать:

Это решение для этой задачи .

Задание на английском языке:
Найти число естественных решений (x≥1, y≥1) из неравенства x²+y² < n, где 0 < n < 2147483647.Например, для n=10 существует 4 решения: (1,1), (1,2), (2,1), (2,2).

Ввод
В первой строке ввода указано количество тестов k.В следующих строках k приведены значения n.

Выход
В выходных данных вы должны отобразить в отдельных строках количество натуральных решенийнеравенство.

Пример

Ввод:

2
10
11

Выход:

4
6

Answer 1

Ваше решение кажется быстрым уже.Основная возможность сократить затрачиваемое время - это подавить вызов до sqrt в цикле.Это получается, если учесть, что значение a = sqrt(n - (i * i)) не сильно меняется от одной итерации к следующей.

Вот код:

    r = 0;
    p = sqrt(n);
    if ((p*p) == n) p--;
    a = p;
    for (long long i = 1; i <= p; i++)
    {
        while ((n-i*i) <= a*a) {
            --a;
        }
        r += a;
    }