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→∞limr2D(r)π因此若能快速算出较大整数rrr对应的D(r)D(r)D(r)就可用来估计π\piπ的值。题目要求对于给定的若干整数nkn_knk1≤nk≤1081\le n_k\le 10^81≤nk≤108输出nkn_knk及其对应的D(nk)D(n_k)D(nk)。输入格式输入文件包含多行每行一个整数nkn_knk1≤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次简单整数比较与加减在合理时间内可完成。本题还体现了数学推导与算法优化的结合是计数类问题的常用思路。

UVa 1549 Lattice Point

相关推荐

像素越小画质越差？神经ISP说：0.35μm也能分辨率翻倍

车载新诊断框架SOVD---SOVD服务器自动发现机制

DM8归档介绍--达梦数据库

更多资讯

吊车是特种工吗？证书过期了不知道怎么复审延期怎么办？

电工证在运城哪里考2026河南最新政策全知道

深圳高级电工证报名能用电子证书吗？外省证也能转过来！

宜兴电工证哪里报名好良心建议

南昌高压电工证考试地址2026河南最新政策怎么选培训机构

沙洋县电工证培训值不值得考？学历不高也能报名，看这里就明白了

今日更新

安监局电工证分数查询怎么查才能知道含金量高不高

新疆电工作业干活累吗良心建议助你避开考不过的坑

中牟县电工证怎么报名外省证能转吗

本周精选

安监局电工证分数查询怎么查才能知道含金量高不高

新疆电工作业干活累吗良心建议助你避开考不过的坑

中牟县电工证怎么报名外省证能转吗

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？

相关推荐

像素越小画质越差？神经ISP说：0.35μm也能分辨率翻倍

车载新诊断框架SOVD---SOVD服务器自动发现机制

DM8归档介绍--达梦数据库

更多资讯

吊车是特种工吗？证书过期了不知道怎么复审延期怎么办？

电工证在运城哪里考2026河南最新政策全知道

深圳高级电工证报名能用电子证书吗？外省证也能转过来！

宜兴电工证哪里报名好良心建议

南昌高压电工证考试地址2026河南最新政策怎么选培训机构

沙洋县电工证培训值不值得考？学历不高也能报名，看这里就明白了

今日更新

安监局电工证分数查询怎么查才能知道含金量高不高

新疆电工作业干活累吗 良心建议助你避开考不过的坑

中牟县电工证怎么报名外省证能转吗

本周精选

安监局电工证分数查询怎么查才能知道含金量高不高

新疆电工作业干活累吗 良心建议助你避开考不过的坑

中牟县电工证怎么报名外省证能转吗

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？

新疆电工作业干活累吗良心建议助你避开考不过的坑

新疆电工作业干活累吗良心建议助你避开考不过的坑