版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！
title: "题解 - [Luogu P2508] [HAOI2008] 圆上的整点" categories:
求一个给定的圆 $(x^2+y^2=r^2)$, 在圆周上有多少个点的坐标是整数
r
整点个数
4
4
$r\leq 2000 000 000$
显然我们只需要考虑第一象限的情况, 设
$$ r^2=2^{2\alpha2}\prod{p\in{x\in\text{Prime}^+|x=4k+3}}p^{2\alphap}\prod{q=\in{x\in\text{Prime}^+|x=4k+1}}q^{2\alpha_q} $$
我们知道任意素数都能分解为一对共轭的 Gauss 整数的乘积, 且由 Fermat 二平方和定理, 只有 $q$ ($4k+1$ 型素数) 能分解为两正整数的平方和
不难发现答案即为
$$ \prod_{q=\in{x\in\text{Prime}^+|x=4k+1}}(2\alpha_q+1) $$
最后乘 4 即为所求
$O\left(\sqrt{r}\right)$