跳转至

P2508 [HAOI2008]圆上的整点

T22:43:00+08:00 洛谷： P2508 【HAOI2008】圆上的整点 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

Lv1 暴力枚举x 20pts

「思路」

暴力出奇迹 没有奇迹。

得到一个象限 乘 4，加上四个坐标轴；或者求1/8圆 乘 8，加上四个坐标轴。

「码」

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <cmath>

#define ll long long

using namespace std;

bool isInteger(const double &x) {
    return x == (ll)x;
}

int main() {
    int r; cin >> r;

    int cnt = 0;
    for (int x = 1; x <= r; x++) {
        if (isInteger(sqrt((ll)r*r - (ll)x*x))) {
            cnt++;
        }
    }
    cout << (cnt << 2) << endl;
    return 0;
}

Lv2 枚举本原勾股数 100pts

「思路」

本原勾股数公式：

\[ \Large \begin{cases} a = m^2 - n^2\\ b = 2mn\\ c = m^2 + n^2 \end{cases} \]

其中 \(m, n \in \N^*, m < n（a, b, c>0）\) 且满足以下条件：

  1. \(gcd(m, n) = 1\)
  2. \(m\) 与 \(n\) 奇偶性不同

本原勾股数就是相互互质的勾股数。

易有：

\[ \Large m = \sqrt{c - n^2} \]

于是可以稍作变形：

\[ \Large \begin{cases} a = c^2 - 2n^2\\ b = 2n\sqrt{c-n^2}\\ c = c \end{cases} \]

这样就可以枚举 \(n\)，然后根据 \(c\) 的值计算出 \(m\)，检查是否合法。

合法即需要以下条件：

  1. \(c - n^2\) 为完全平方数（这样才能开方出正整数 \(m\)）
  2. \(gcd(\sqrt{c - n^2}, n) = 1\)（同本原勾股数公式条件1）
  3. \(\sqrt{c - n^2}\) 与 \(n\) 奇偶性不同（同本原勾股数公式条件2）

那么对于输入的任意一个半径，它上面的格点所对应的勾股数都有可能是由某一个本原勾股数乘以某一倍数 \(k\) 得到的，即 \(r = k \cdot c\)，那么我们就可以枚举每一个 \(c\)（也就是枚举 \(r\) 的每一个因数），再对应的 \(c\) 下枚举 \(n\) 得到该 \(c\) 下满足条件的数量，再累加起来即可。

「码」

C++
 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
37
38
#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

inline int gcd(const int &a, const int &b) {
    return b ? gcd(b, a%b) : a;
}

inline bool isSquare(const int &x) {
    return (int)sqrt(x)*(int)sqrt(x) == x;
}

void solve(const int &c, int &cnt) {
    for (int n = 1; 2*n*n < c; n++) {
        if (isSquare(c - n*n) && gcd(sqrt(c - n*n), n) == 1 && ((int)sqrt(c - n*n)%2 != n%2)) {
            cnt++;
        }
    }
}

Math.sqrt()

int main() {
    int r; cin >> r;

    int cnt = 0;
    for (int i = 1; i <= sqrt(r); i++) {
        if (r % i) continue;
        solve(i, cnt);
        if (i*i != r) solve(r/i, cnt);
    }

    cout << ((cnt<<1)<<2) + 4 << endl;

    return 0;
}

Lv3 高斯素数 100pts

「思路」

1. 复平面

如果借助复平面来表示格点，则对于以原点为圆心半径为 \(r\) 的圆上任意格点（对应的也就是一个复数 \(z\)）都有：

\[ \large z \cdot \bar{z} = r^2 \]

那么问题也就发生了转化：

将 \(R^2\) 分解、重组为 \(z\) 和 \(\bar{z}\) 的方案数。

2. 高斯素数

引入一个概念 高斯素数，正如 素数 为不能再分解因数的数，高斯素数 就是复平面上不能再继续分解的数，例如 \(3 + 4i = (2+i)\cdot(2+i)\) 可以分解，而 \(2+i\) 不能再继续分解，它就是一个 高斯素数。

容易知道 \(\overline{z_1 z_2 \cdots z_n} = \bar{z_1} \bar{z_2} \cdots \bar{z_n}\)，那么如果我们将 \(z\) 与 \(\bar{z}\) 彻底分解为一系列 高斯素数 之积，问题也就再次转化：

将这一系列 高斯素数 分为两组，一组中的元素为对应另一组元素的 共轭复数 的方案数。

3. 分解 \(r^2\) 为高斯素数

那么，我们怎么知道 \(r^2\) 如何分解为 高斯素数？

首先我们可以将 \(r^2\) 按照唯一分解定理分解：

\[ \large r^2 = p_1^{k_1} p_2^{k_2} \cdots p_k^{k_k} \]

这里面的所有 \(p_i\) 可以分为两类（除去2）：

  1. 形如 \(4k + 1(k \in \N^*)\) 型的质因数
  2. 形如 \(4k + 3(k \in \N^*)\) 型的质因数

\(4k\)，\(4k+2\) 都不是素数。

这两种质因数在分解为共轭复数的过程中的表现是不同的。

1）\(4k + 1\) 型质因数的分解

引入 费马平方和定理：

只有形如 \(4k+1(k \in \N^*)\) 型的素数能够分解为两个正整数的平方和。（除了2，也就是对奇质数成立[质数除了2也都是奇数]）

能表示为 两个正整数的平方和 也就自然可以表示为 一对共轭复数之积 ：

\[ \large p = a^2 + b^2 = a^2 - (-b^2) = a^2 - (bi)^2 = (a + bi)(a - bi) \]

而且这 一对共轭复数 还都是 高斯素数。

对于这类素数的次方即 \(p^k\) 分解得到的 共轭高斯素数 按照之前所说分成两组的方案数就是 k+1 种。

可以理解为这样一个过程：

如果令 \(p = z \cdot \bar{z}\)。

起始的一种方案：A组全为 \(z\)，B组全为 \(\bar{z}\)。

此后每次交换一对共轭高斯素数，由于每对高斯素数都是相同的，所以无关顺序。

也就是A组中有0个、1个、2个...k个 \(\bar{z}\)，一共 k+1 种。

2）\(4k + 3\) 型质因数的分解

还有另一个结论：

形如 \(4k + 3(k \in \N^*)\) 型的素数都是高斯素数，例如7、11、19等都不能再分解为两个复数之积。

那么如果它的指数为奇数，显然不论放在哪一组都无法达到两组分别乘积得到的复数相互共轭的结果，也就是有 \(0\) 种方案。

只有在它的指数为偶数的时候，平分到两组中才行，那自然也就是只有 1 种方案。

也就是 这类高斯素数本身是它自己的共轭复数。

不过呢！！！对于这道题来说不用管！！！

为什么呢，因为题目输入的是 \(r\)，我们要分解的 \(r^2\) 的每一个质因数的指数注定都是偶数：

\[ \large 若设 \;\;\;\; r = p_1^{k_1} p_2^{k_2} \cdots p_k^{k_k}\;\;\;\; 则\;\;\;\; \large r^2 = p_1^{2k_1} p_2^{2k_2} \cdots p_k^{2k_k} \]

4. 乘法原理 以及 -1，i 和 -i！

那接下来的事情，就是将每个质因数的方案数成在一起即可。

同时其实刚才的分解并不全，正如 \(12 = 3\times2^2 = 3\times(-2)^2\) 一样，刚才我们考虑的高斯素数只是实部大于0的。

而对于任意一种 \(z \cdot \bar{z}\) 来说 \((-z) \cdot (\overline{-z})\)，\((iz) \cdot (\overline{iz})\)，\((-iz) \cdot (\overline{-iz})\) 也都是一种方案。

在几何直观上的复平面中也就是：关于y轴对称、逆时针旋转90°、顺时针旋转90°。

所以还要乘以四才是最终的格点数量。

5. 关于2

（挖个坑，过一段时间再填

6. 对于本题的一些优化

由于 \(r^2\) 的所有指数都是 \(r\) 的两倍，故不必分解 \(r^2\)，直接分解 \(r\) 即可。

那么原本的 k+1 也就成了 k * 2+1，位运算加速也就是 k<<1|1。

「码」

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>

using namespace std;

int main() {
    int r; cin >> r;

    int ans = 1;
    for (int i = 2; i*i <= r; i++) {
        if (r % i == 0) {
            int cnt = 0;
            do {r /= i; cnt++; } while (r % i == 0);
            if (i % 4 == 1) ans *= cnt<<1|1;
        }
    }
    if (r != 1 && r % 4 == 1) ans *= 1<<1|1;
    cout << (ans<<2) << endl;

    return 0;
}

参考

来，咱们一起找出所有勾股数组~ - 知乎 (zhihu.com)

勾股数有有限多组还是无限多组？ - 知乎 (zhihu.com)

走进数论——神奇的勾股数组 - Akarui 的博客 - 洛谷博客 (luogu.com.cn)

分解质因数 - OI Wiki (oi-wiki.org)

高斯素数有类似于素数定理的分布律吗？ - 知乎 (zhihu.com)

【官方双语】隐藏在素数规律中的π_哔哩哔哩_bilibili

评论