BZOJ 1041 (YZOJ 3460) 圆规问题

圆规问题

时间限制:1000MS 内存限制:262144KB

  • 问题描述

小 C 有一个圆规,他经常用圆规在纸上作图。

有一天,小 C 准备在一个单位网格纸上作一个圆。他以某个格点为圆心,作了一个半径为 \(R\) 的圆。接着,他将圆经过的所有格子涂成黑色。注意:只有圆经过了一个格子的内部才能涂黑,只经过格子的边界不涂黑。小 C 的问题是:对于给定的半径为 \(R\) 的圆,共有多少个格子被涂黑?

这是一个 \(R=10\)的实例:

左图为小 C 作的圆,右图是将圆经过的格子涂黑后的图。可以看出,\(R=10\)时,共有 68 个格子被涂黑。

给定\(N\),计算被涂黑的格子数目。

  • 输入格式

输入文件包含一个整数\(R\),\(1 \leq R \leq 2,000,000,000\)

  • 输出格式

将被涂黑的格子数目输出到文件中。

  • 样例输入

  • 样例输出

 


 

 

不错,可惜这个是人家大神的做法,我的话绝对想不出来。

 

然后,我想起了一个两年前看到的视频

https://www.youtube.com/watch?v=NaL_Cb42WyY

Translated: https://www.bilibili.com/video/av12131743

 

首先定义 \(\chi (n) = \left\{ {\begin{array}{*{20}{c}}
0&{n\bmod 2 \equiv 0}\\
1&{n\bmod 4 \equiv 1}\\
{ – 1}&{n\bmod 4 \equiv – 1}
\end{array}} \right.\)

然后,对于半径为\(\sqrt{R}\)的圆,其经过整点个数为\(4 \cdot \sum\limits_{i|R} {\chi (i)} \)

有了这个结论,程序就不难实现。

 

只需要把\(R\)进行质因数分解,一般质因数分解最差情况下\(O(R)\)当且仅当R为质数,特判一下即可做到\(O(\sqrt{R})\)

然后DFS出\(R^2\)的所有因数(遍历\(R\)的质因数时,把其指数扩大一倍遍历即可),因为\(4 \cdot 10^{18}\)的因数个数仅为\(399\),所以理论下不存在风险。

 

 

base[][]没什么用,忽略吧

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注