Найти количество пар натуральных чисел, удовлетворяющих неравенству
Я пытаюсь решить проблему программирования, где я должен отобразить число положительных целых решений неравенства 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
Решение
Ваше решение кажется быстрым уже. Основная возможность сократить затрачиваемое время — это подавить вызов 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;
}
Другие решения
Других решений пока нет …