UVa 1549 Lattice Point

题目描述格点是指在二维xyxyxy平面中坐标(x,y)(x, y)(x,y)均为整数的点。定义集合P(r){(x,y)∣x2y2≤r2, (x,y) 为平面上的格点} P(r)\{(x,y)\mid x^2y^2\le r^2,\ (x,y)\text{ 为平面上的格点}\}P(r){(x,y)∣x2y2≤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)对于r108r10^8r108完全不可行。我们需要利用圆的对称性和整数运算来加速。由于圆关于xxx轴、yyy轴以及原点都对称我们可以只统计第一象限含坐标轴的格点数再通过对称性乘以444并调整原点计数。具体地对于x0x0x0且y0y0y0的点每个点对应四个对称点(±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)x1…⌊r⌋x1\dots\lfloor r\rfloorx1…⌊r⌋。原点单独111个。因此D(r)14⌊r⌋4∑x1⌊r⌋⌊r2−x2⌋ D(r)14\lfloor r\rfloor4\sum_{x1}^{\lfloor r\rfloor}\left\lfloor\sqrt{r^2-x^2}\right\rfloorD(r)14⌊r⌋4x1∑⌊r⌋​⌊r2−x2​⌋当rrr为整数时⌊r⌋r\lfloor r\rfloorr⌊r⌋r上式为D(r)14r4∑x1r⌊r2−x2⌋ D(r)14r4\sum_{x1}^{r}\left\lfloor\sqrt{r^2-x^2}\right\rfloorD(r)14r4x1∑r​⌊r2−x2​⌋其中当xrxrxr时根号下为000该项为000所以也可以只加到r−1r-1r−1但统一加到rrr不影响结果。问题的关键转化为快速计算S(r)∑x1r⌊r2−x2⌋ S(r)\sum_{x1}^{r}\left\lfloor\sqrt{r^2-x^2}\right\rfloorS(r)x1∑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​⌋是单调不增的。我们设yryryr然后从x1x1x1开始遍历。对于每个xxx我们不断减小yyy直到满足y2x2≤r2y^2x^2\le r^2y2x2≤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)。下面验证算法的正确性。初始时x1x1x1yryryr。显然r21r2r^21r^2r21r2所以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//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;// 计算 D(r)r 为非负整数longlongcountLatticePoints(longlongr){if(r0)return1;longlongr2r*r;longlongyr;longlongsum0;for(longlongx1;xr;x){while(y*yx*xr2)--y;// 调整 y 使 (x,y) 在圆内sumy;// 累加该列上格点数y1..floor(sqrt(...))}// 原点1个 坐标轴上4r个 四个象限内4*sum个return14*r4*sum;}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);longlongn;while(cinn){coutn\n;coutcountLatticePoints(n)\n;}return0;}总结本题的核心在于利用对称性将四象限计数转化为第一象限求和并利用整数递推避免浮点精度问题将O(r2)O(r^2)O(r2)的暴力枚举优化为O(r)O(r)O(r)的线性扫描。关键技巧是维护一个单调递减的yyy指针使得每一列的yyy值均可通过O(1)O(1)O(1)次调整得到。该方法在r108r10^8r108时循环次数约为2×1082\times 10^82×108次简单整数比较与加减在合理时间内可完成。本题还体现了数学推导与算法优化的结合是计数类问题的常用思路。