题解 - [Luogu P2508] [HAOI2008] 圆上的整点

发表于 更新于 分类于 ， 本文字数： 242 阅读时长 ≈ 1 分钟

题目链接

原始题面

题目描述

求一个给定的圆 \((x^2+y^2=r^2)\), 在圆周上有多少个点的坐标是整数

输入格式

r

输出格式

整点个数

样例 #1

样例输入 #1

1
4

样例输出 #1

1
4

提示

\(r\leq 2000 000 000\)

解题思路

显然我们只需要考虑第一象限的情况，设

\[ r^2=2^{2\alpha_2}\prod_{p\in\{x\in\text{Prime}^+|x=4k+3\}}p^{2\alpha_p}\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)\)

代码参考

Show code

Luogu_P2508view raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/*
 * @Author: Tifa
 * @Description: From <https://github.com/Tiphereth-A/CP-archives>
 * !!! ATTENEION: All the context below is licensed under a 
 *  GNU Affero General Public License, Version 3.
 *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
 */
#include <bits/stdc++.h>
using i64 = int64_t;
#define for_(i, l, r, vars...) \
  for (decltype(l + r) i = (l), i##end = (r), ##vars; i <= i##end; ++i)
using namespace std;
auto solve([[maybe_unused]] int t_ = 0) -> void {
  i64 r;
  cin >> r;
  i64 ans = 1;
  for_(i, 2, (i64)sqrt(r), cnt) {
    if (i > r) break;
    if (r % i) continue;
    cnt = 0;
    while (r % i == 0) {
      r /= i;
      ++cnt;
    }
    if (i % 4 > 1) continue;
    ans *= cnt * 2 + 1;
  }
  if (r > 1 && r % 4 == 1) ans *= 3;
  cout << ans * 4;
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  solve(0);
  return 0;
}