找出满足不等式的正整数对的数量

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;
}

编辑：

这是 this task 的解决方案。

英语任务：
求不等式 x²+y² < n 的自然解数 (x≥1, y≥1)，其中 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;
    }

找出满足不等式的正整数对的数量

Find the number of pairs of positive integers satisfying the inequality

c++

geometry

inequality

编辑：