自动搬运

查看原文

来自洛谷，原作者为

	ivyjiao 复活了

搬运于2025-08-24 22:52:29，当前版本为作者最后更新于2023-11-16 20:23:20，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

怎么没找到 $T$ 的数据范围啊？在这里钦定 $1\leq T\leq 25000$ 吧。

根据初中数学可以得出，原问题等于求： $x^2+y^2\leq n^2$ 的整数对 $(x,y)$ 的有序对数。

这题我想了 1h 的线性做法，然后发现好像没有。

这题我们显然可以打一个 $O(Tn^2)$ 的暴力出来：

#include<bits/stdc++.h>
using namespace std;
int n,sum,a[25001];
int main(){
    while(cin>>n&&n){
        if(!a[n]){
            sum=0;
            for(int i=1;i<=n;i++){
                for(int j=1;i*i+j*j<=n*n;j++) sum++;
            }
            a[n]=4*sum+4*n+1;
            cout<<4*sum+4*n+1<<endl;
        }
        else cout<<a[n]<<endl;
    }
}

这样显然是不行的，$T$ 取 $25000$ 然后每个 $n$ 不同分分钟可以给你卡到 $n^3$ 级别，根本过不了。

哎？怎么过了？肯定是因为数据水，我们接着考虑怎么优化：

容易发现每次的内层循环中，$i^2$ 的值是一定的，$j^2$ 的值可以通过预处理整出来，然后每次二分求解，所以内层可以被优化到 $\log n$ 级别。

时间复杂度 $O(Tn\log n)$。

#include<bits/stdc++.h>
using namespace std;
int n,sum,a[25001],b[25001];
int main(){
    for(int i=1;i<=25000;i++) b[i]=i*i;
    while(cin>>n&&n){
        if(!a[n]){
            sum=0;
            for(int i=1;i<=n;i++){
                int l=0,r=25000;
                while(l<r){
                    int mid=l+r+1>>1;
                    if(b[mid]<=n*n-i*i) l=mid;
                    else r=mid-1;
                }
                sum+=l;
            }
            a[n]=4*sum+4*n+1;
            cout<<4*sum+4*n+1<<endl;
        }
        else cout<<a[n]<<endl;
    }
}

然而这种做法似乎也过不去，因为还是那样，如果 $T$ 取 $25000$ 然后每个 $n$ 不同分分钟可以给你卡满，而卡满的情况下大约需要跑 $10^{10}$ 次，也过不了。

哎？怎么又过了？肯定是因为数据水，我们接着考虑怎么优化：

这时候肯定就有人说了：你前面说没有线性做法，现在又说单 $\log$ 过不去，难道除了线性有什么东西比单 $\log$ 还快吗？

确实没有，但是我们充分发扬人类智慧，直观感受一下：

我们感觉到：在矩形中，包含在圆里的点的数量一定比不包含在圆里的点的数量多很多，也就是说，设 $m=n\times 2+1$，最终的答案一定是 $m^2-4\times$ 一个很小的数字。

我们考虑枚举每一个不在圆里的点，也就是找出那个很小的数字，这个跟那个暴力差不多，时间复杂度 $O(Tn^2)$，但是严重跑不满，最终过了。

#include<bits/stdc++.h>
using namespace std;
int n,sum,a[25001];
int main(){
    while(cin>>n&&n){
        if(!a[n]){
            sum=0;
            for(int i=1,j=n;i<=n;i++){
				j=n;
                while(i*i+j*j>n*n) sum++,j--;
            }
            a[n]=(n*2+1)*(n*2+1)-4*sum;
            cout<<(n*2+1)*(n*2+1)-4*sum<<endl;
        }
        else cout<<a[n]<<endl;
    }
}

附极限数据一组，供大佬们调试用。