企业官网建设流程全解析

题目描述

格点是指在二维xyxyxy平面中坐标(x,y)(x, y)(x,y)均为整数的点。定义集合
P(r)={(x,y)∣x2+y2≤r2, (x,y) 为平面上的格点} P(r)=\{(x,y)\mid x^2+y^2\le r^2,\ (x,y)\text{ 为平面上的格点}\}P(r)={(x,y)∣x2+y2≤r2,(x,y)为平面上的格点}
并用D(r)D(r)D(r)表示P(r)P(r)P(r)中元素的个数。已知当rrr较大时，D(r)D(r)D(r)与圆面积πr2\pi r^2πr2有如下关系：
lim⁡r→∞D(r)r2=π \lim_{r\to\infty}\frac{D(r)}{r^2}=\pir→∞lim​r2D(r)​=π
因此若能快速算出较大整数rrr对应的D(r)D(r)D(r)，就可用来估计π\piπ的值。

题目要求对于给定的若干整数nkn_knk​（1≤nk≤1081\le n_k\le 10^81≤nk​≤108），输出nkn_knk​及其对应的D(nk)D(n_k)D(nk​)。

输入格式

输入文件包含多行，每行一个整数nkn_knk​（1≤nk≤1081\le n_k\le 10^81≤nk​≤108）。

输出格式

对于第kkk个输入整数nkn_knk​，先在第2k−12k-12k−1行输出nkn_knk​，再在第2k2k2k行输出D(nk)D(n_k)D(nk​)。

样例

输入

1 2 3 10000 10000000

输出

1 5 2 13 3 29 10000 314159053 100000000 31415926535867961

题目分析

直接枚举所有格点检查是否落在圆内，时间复杂度为O(r2)O(r^2)O(r2)，对于r=108r=10^8r=108完全不可行。我们需要利用圆的对称性和整数运算来加速。

由于圆关于xxx轴、yyy轴以及原点都对称，我们可以只统计第一象限（含坐标轴）的格点数，再通过对称性乘以444并调整原点计数。具体地，对于x>0x>0x>0且y>0y>0y>0的点，每个点对应四个对称点（(±x,±y)(\pm x,\pm y)(±x,±y)），共444个。坐标轴上的非原点格点共有4⌊r⌋4\lfloor r\rfloor4⌊r⌋个（(±x,0)(\pm x,0)(±x,0)和(0,±x)(0,\pm x)(0,±x)，x=1…⌊r⌋x=1\dots\lfloor r\rfloorx=1…⌊r⌋）。原点单独111个。因此：
D(r)=1+4⌊r⌋+4∑x=1⌊r⌋⌊r2−x2⌋ D(r)=1+4\lfloor r\rfloor+4\sum_{x=1}^{\lfloor r\rfloor}\left\lfloor\sqrt{r^2-x^2}\right\rfloorD(r)=1+4⌊r⌋+4x=1∑⌊r⌋​⌊r2−x2​⌋
当rrr为整数时，⌊r⌋=r\lfloor r\rfloor=r⌊r⌋=r，上式为：
D(r)=1+4r+4∑x=1r⌊r2−x2⌋ D(r)=1+4r+4\sum_{x=1}^{r}\left\lfloor\sqrt{r^2-x^2}\right\rfloorD(r)=1+4r+4x=1∑r​⌊r2−x2​⌋
其中当x=rx=rx=r时，根号下为000，该项为000，所以也可以只加到r−1r-1r−1，但统一加到rrr不影响结果。

问题的关键转化为快速计算
S(r)=∑x=1r⌊r2−x2⌋ S(r)=\sum_{x=1}^{r}\left\lfloor\sqrt{r^2-x^2}\right\rfloorS(r)=x=1∑r​⌊r2−x2​⌋
若直接对每个xxx使用浮点数开平方，r2r^2r2最大可达101610^{16}1016，双精度浮点数无法精确表示所有整数，会导致舍入误差。因此必须采用整数方法。

解题思路

注意到当xxx从111增大到rrr时，⌊r2−x2⌋\left\lfloor\sqrt{r^2-x^2}\right\rfloor⌊r2−x2​⌋是单调不增的。我们设y=ry=ry=r，然后从x=1x=1x=1开始遍历。对于每个xxx，我们不断减小yyy直到满足y2+x2≤r2y^2+x^2\le r^2y2+x2≤r2，此时yyy就是要求的⌊r2−x2⌋\left\lfloor\sqrt{r^2-x^2}\right\rfloor⌊r2−x2​⌋。然后将yyy累加到S(r)S(r)S(r)中。

因为yyy在遍历过程中只会减小，且每次最多减小111，总共减小的次数不超过rrr次。因此整个循环的时间复杂度为O(r)O(r)O(r)，空间复杂度为O(1)O(1)O(1)。

下面验证算法的正确性。初始时x=1x=1x=1，y=ry=ry=r。显然r2+1>r2r^2+1>r^2r2+1>r2，所以yyy会不断减小直到满足不等式。当xxx增大时，r2−x2r^2-x^2r2−x2变小，所以满足条件的最大yyy不会增大，因此yyy的单调性得到保证，利用双指针（一个指针xxx递增，一个指针yyy递减）可以线性完成。

最后将S(r)S(r)S(r)代入公式即可得到D(r)D(r)D(r)。对于输入中每个nnn，独立调用该函数计算。

代码实现

// Lattice Point// UVa ID: 1549// Verdict: Accepted// Submission Date: 2026-06-20// UVa Run Time: 0.000s//// 版权所有（C）2026，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;// 计算 D(r)，r 为非负整数longlongcountLatticePoints(longlongr){if(r==0)return1;longlongr2=r*r;longlongy=r;longlongsum=0;for(longlongx=1;x<=r;++x){while(y*y+x*x>r2)--y;// 调整 y 使 (x,y) 在圆内sum+=y;// 累加该列上格点数（y=1..floor(sqrt(...))）}// 原点1个 + 坐标轴上4r个 + 四个象限内4*sum个return1+4*r+4*sum;}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);longlongn;while(cin>>n){cout<<n<<'\n';cout<<countLatticePoints(n)<<'\n';}return0;}

总结

本题的核心在于利用对称性将四象限计数转化为第一象限求和，并利用整数递推避免浮点精度问题，将O(r2)O(r^2)O(r2)的暴力枚举优化为O(r)O(r)O(r)的线性扫描。关键技巧是维护一个单调递减的yyy指针，使得每一列的yyy值均可通过O(1)O(1)O(1)次调整得到。该方法在r=108r=10^8r=108时，循环次数约为2×1082\times 10^82×108次简单整数比较与加减，在合理时间内可完成。本题还体现了数学推导与算法优化的结合，是计数类问题的常用思路。