圆规问题

时间限制：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[][]没什么用，忽略吧