给定数字N,有多少对数字的平方和小于或等于N？

Question

让我们定义F(N)作为对不同的正整数的数目(A,B) ,使得甲² + B ² ≤N和A <B .

如果N = 5,唯一可能的这样的对是(1,2),对于N = 10,对是2: (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;