背景
深夜，一位退役 OIer 正坐在电脑前恰着零食喝着快乐水逛着B站。
突然，emptyset 发现了一则十分通俗易懂并且相当有趣的双语科普视频。
emptyset 总记得见过这问题，迅速打开洛咕一看，我靠，何止是见过，明晃晃赤裸裸的“历史分数 20”惨不兮兮的挂在那里。吓得 emptyset 赶紧打开记事本码了起来。
emptyset 想着自己退役了也没给洛咕有什么贡献，于是就打算写一篇通（垃）俗（圾）易（难）懂（读）的题解。
思路
PART I
假如我们在研究这样一类问题：以原点为圆心，以 \sqrt N 为半径的圆上有多少个整点。
我们转化下，其实就是：有多少个整数对 (a,b) 满足 a^2+b^2=N。
然而，研究二元关系总是不方便的，我们可以将二维平面看做全体复数。
如果你没学过复数，可以先这样理解，平面直角坐标系上的点 (a,b) 对应复数 a+bi，其中 i 是虚数单位，满足 i^2=-1。
特别的，如果虚数 a+bi 中 a,b 均为整数，我们又称其为高斯整数。
注意到 a^2+b^2=N 等价于 (a+bi)(a-bi)=N，因此，问题又可以转化为：有多少个高斯整数 z 满足其本身与其共轭复数 \overline{z} 的乘积是 N。
PART II
既然谈到了高斯整数相乘为 N，我们应该康康一个数 N 如何在高斯整数上分解。
我们都知道，一个数 N 在整数范围内有唯一分解式，即表达为若干个因子的乘积，而其中每个因子都不能再分，这些因子也就是我们说的素数。
当然，你给其中一个因子乘以 -1，给另一个因子也乘以 -1（-1\times -1=1），这样的分解式依然成立。
在高斯整数范围内，一个整数 N 也可以表达为若干个复数因子的乘积，而其中每个因子在高斯整数上不能再分，这些因子也就是高斯素数。
e.g. 整数 5=(2+i)(2-i)，而 2+i 等就不能再分了，也就是说 2+i 这样的就是高斯素数。
当然，这一回，你不但可以给其中一个因子乘以 -1，给另一个因子乘以 -1，你还可以给其中一个乘以 i，另一个乘以 -i（i\times -i=1），这样分解式依然成立。
e.g. 5=(2+i)(2-i)
=(-2-i)(-2+i)$ //注：一个因子乘以$-1$，另一个因子乘以$-1
=(2i-1)(-2i-1)$ //注：一个因子乘以 $i$，另一个因子乘以$-i
所以，想要一个数在高斯整数上分解，我们考虑先将 N 分解为若干个素数的乘积，再将其中的非高斯素数进一步分解。
PART III
那么我怎么知道一个素数是不是高斯素数呢？
我们可以借助费马平方和定理。
费马平方和定理：奇素数 p 可以表示为两个正整数的平方和，当且仅当 p 是 4k+1 型的。并且在不考虑两个正整数顺序的情况下，这个表示方法唯一。
证明留作习题，读者自证亦不难有点难，当然，其实是有相当初等的证法的。
通过该定理我们得知，
$4k+1$ 型的素数可以恰好被分解成一对共轭复数的乘积，因此，以$\sqrt5,\sqrt{13},\sqrt{17}\cdots$为半径的圆上有整点（实际上观察可知恰好是 $8$ 个整点，原因后文再讲）；
而剩下一个素数 $2$ 则比较特殊，她的确可以分解成一对共轭复数 $(1+i)(1-i)$，有趣的是这两个复数除了共轭，他们的夹角还恰好为 $90\degree$。
--------
#### PART IV
如果用 $p$ 表示 $4k+1$ 型素数，$q$ 表示 $4k+3$ 素数（即高斯素数），那么我们可以将 $N$ 表示为这样的形式：
$$\large N=2^n\prod_{q_i=4k+3}q_i^{m_i}\prod_{p_j=4k+1}p_j^{k_j}$$
其中，每一个 $p_i$ 是可以分解为一对共轭复数的。
现在我们的目的是求将 $N$ 表示为一对共轭复数的乘积有多少种方法，那么分别讨论每一种素数：
- $4k+1$ 型素数 $p_j$ 的贡献
对于每一个 $p_j$，可以分解成 $z_j$ 和 $\overline{z_j}$，
我们可以将 $z_j$ 分配给 $N$ 的第一个因子，将 $\overline{z_j}$ 分配给 $N$ 的第二个因子（这样才能保证 $N$ 的两个因子是共轭的），
也可以将 $\overline{z_j}$ 分配给第一个因子，将 $z_j$ 分配给第二个因子。
也就是说，每一个 $p_j$ 可以有 $2$ 种分配方式。
更进一步的，对于 $p_j^{k_j}$，我们可以给第一个因子分配 $0$ 个 $z_j$、$1$ 个 $z_j\cdots$一直到 $k_j$ 个 $z_j$。
**也就是说，每一个 $p_j^{k_j}$ 可以有 $k_j+1$ 种分配方式。**
- $4k+3$ 型素数即高斯素数 $q_i$ 的贡献
> 在此之前，相信大家都知道如果一个复数没有虚部，那么该复数的共轭复数就是他本身，因为若 $z=a+0i$，$\overline z=a-0i=z$。
对于 $q_i^{m_i}$，我们想要把他分成共轭的两个因子的乘积，有多少种方案呢？
显然，如果 $2\mid m_i$，那么我们给每个因子分配 $m_i/2$ 个 $q_i$，两个因子相等，自然也就共轭了，分配方案数为 $1$。
如果 $2\nmid m_i$，哦，完蛋，因为你怎么分也不能把 $q_i^{m_i}$ 分成一对共轭复数的乘积，方案数为 $0$。
**也就是说，$m_i$ 是偶数没什么影响，只要有一个 $m_i$ 是奇数，那么方案数立即归零，这个圆上没有整点。**
- 素数 $2$ 的贡献
在讨论 $2$ 的问题前，请先注意一个问题：
> 正如前文所说，对于将 $N$ 表示为 $z\cdot\overline{z}$ 的每一种方案，$N$ 还可以表示为 $-z\cdot-\overline{z}$、$iz\cdot -i\overline{z}$、$-iz\cdot i\overline{z}$。
>也就是说，最终的方案数是要乘以 $4$ 的。
>对应到几何关系上，等于说每得到一个圆上的整点，还可以将它绕原点旋转 $90\degree,180\degree,270\degree$，转完的点还是在圆上的，这是乘以 $4$ 的等价解释。
现在再来看，我们说过，每一个 $2$ 虽然可以表示为 $(1+i)(1-i)$，看似提供了 $2$ 种分配方案（前者给第一个因子 或 前者给第二个因子 这两种），但是由于 $(1+i)$ 与 $(1-i)$ 的夹角是 $90\degree$，如果考虑 $2$ 的贡献会与之后的 “乘以 $4$” 计重，所以不应该考虑 $2$ 的贡献。
> 举个例子，半径为 $\sqrt5$ 的圆上有多少个整点，半径为 $\sqrt{10},\sqrt{20},\sqrt{40}$ 的圆上就有多少个整点。
**也就是说，因为最终方案数要乘以 $4$，所以 $2^n$ 不应该产生任何影响。**
------------
#### PART V
好了，现在我们可以看这道题了，在本题中，$N=r^2$，$r$ 是给定的。
假设分解 $r$ 得到
$$r=2^n\prod_{q_i=4k+3}q_i^{m_i}\prod_{p_j=4k+1}p_j^{k_j}$$
那么
$$N=2^{2n}\prod_{q_i=4k+3}q_i^{2m_i}\prod_{p_j=4k+1}p_j^{2k_j}$$
我们很高兴的看到，$N$ 的每一个高斯素数因子 $q_i$ 的指数 $2m_i$ 都是偶数，不用担心归零了，他们不会产生任何影响。
更进一步的，方案数只与 $2k_j$ 有关。
上文提到，每一个 $p_j^{k_j}$ 可以有 $k_j+1$ 种分配方式，那么每一个 $p_j^{2k_j}$ 可以有 $2k_j+1$ 种分配方式。
再考虑上乘以 $4$，得到圆上的整点数为
$$4\prod_{p_j=4k+1}(2k_j+1)$$
复杂度为分解素因数 $\Theta(\sqrt r)$。
### 代码
```cpp
#include <cstdio>
int r;
long long ans = 1;
int main() {
scanf("%d", &r);
for(int i = 2, cnt; i*i <= r; ++i)
if(!(r % i)) {
cnt = 0;
do r /= i, ++cnt; while(!(r % i));
if(i%4 == 1) ans *= cnt<<1|1;
}
if(r != 1 and r%4 == 1) ans *= 3;
printf("%lld\n", ans<<2);
}
```
### p.s
> 好了好了这可能是最后一次在洛咕灌水了，算是最后一件与 OI 有关的事情吧，溜了溜了。