c++ - 给定一个数 N，有多少对数的平方和小于或等于 N？

Question

让我们将 F(N) 定义为不同正整数对的数量 (A,B) 使得 A²+B²≤N 和A 。

如果 N=5 唯一可能的这样的对是 (1,2) 对于 N=10 对是两个:(1,2) 和 (1,3)。

此外我们有 F(13)=3, F(17)=4, F(17)=4, F(20)=5, F(20)=5, F(25)=6, F(100)=31 依此类推，每个数字都是两个不同的非零平方和。

到目前为止，我有以下解决方案:

long long SOLVE(lld n)
{
    long long x=sqrt(n),up=0;
    long long a=x,b=1;
    while(abs(a-(b-1))!=1)
    {

        while(sqr(a)+sqr(b)<=n )
        {
            b++;
        }
        up+=(b-1);
        a--;
    }
    b--;
    up+=(b*(b+1))/2;
    return up;
}
int main()
{
      cout<<number(100);
return 0;
}

相同的数字不可数，因此 (1,1) 和 (2,2) 是无效的元组。相同的组合但不同的顺序只计算一次。因此 (1,2) 和 (2,1) 只算一次。

但是由于N的范围是1，我需要一个更有效的算法或公式来计算这个。有什么技巧可以让我的代码更有效率吗？

Answer 1

在伪代码中:

int count=0;
for (smaller=1; ;++smaller)
{
    maxlarger = floor(sqrt(N-smaller*smaller));
    if (maxlarger <= smaller)
        break;
    count+=(maxlarger-smaller);
}
return count;