P2508 [HAOI2008]圆上的整点

Description

给定一个半径为 $r$ 的圆，求在圆周上坐标为正数的点的个数。

Find

这题好迷啊，我们画几张图试试（图片懒得挂了，可以去 desmos 玩玩）

• $r=1$

$ans = 4$

• $r=2$

$ans = 4$

• $r=3$

$ans = 4$

• $r=4$

$ans = 4$

• $r=5$

$ans=12$

• $r=6$

$ans=4$

我们会发现，毫无规律，大小也不按照 $r$ 的大小排 wtnl

然后一看这标签，没有计算几何，诶

说明我们要推柿子了

Solution 1

推长~长~的柿子

$$\begin{aligned}x^2+y^2&=r^2\\ y^2&=r^2-x^2\\ y^2&=(r+x)(r-x)\\ y^2&=(\gcd(r-x,r+x))^2\cdot \dfrac{r-x}{\gcd(r-x,r+x)}\cdot\dfrac{r+x}{\gcd(r-x,r+x)}\end{aligned}$$
然后我们易得 $\dfrac{r-x}{\gcd(r-x,r+x)},\dfrac{r+x}{\gcd(r-x,r+x)}$ 这两个数为完全平方数（$y^2$ 和 $(\gcd(r-x,r+x))^2$ 都是完全平方数，所以 $\dfrac{r-x}{\gcd(r-x,r+x)}\cdot\dfrac{r+x}{\gcd(r-x,r+x)}$ 就是完全平方数，又因为这两个数的 $\gcd$ 是 $1$，所以这两个数分别为完全平方数）
然后可以推出这两个数分别等于 $\dfrac{r-x}{\gcd(r-x,r+x)},\dfrac{r+x}{\gcd(r-x,r+x)}$
两个数的和就为 $\dfrac{2r}{\gcd(r-x,r+x)}$，我们就得知 $\gcd(r-x,r+x)$ 为 $2r$ 的约数

然后我们就可以开始枚举约数了（枚举 $\sqrt{\dfrac{r-x}{\gcd(r-x,r+x)}}$ 在 $\left[1,\sqrt{\dfrac{r}{\gcd(r-x,r+x)}}\right]$ 的值，然后推导过去 $\dfrac{r-x}{\gcd(r-x,r+x)},\dfrac{r+x}{\gcd(r-x,r+x)}$ 即可）

最后，我们就可以得到代码啦！

#include <bits/stdc++.h>

using namespace std;

long long gcd (long long a, long long b) {return b == 0 ? a : gcd(b, a % b);}

int main () {
    long long r;
    scanf("%lld", &r);
    r *= 2;
    long long ans = 0;
    for (long long i = 1; i * i <= r; i++) {
        if (r % i > 0) 
            continue;
        for (long long j = 1; j * j <= (i >> 1); j++) {
            long long tmp = 1ll * trunc(sqrt(i - (j * j))); // trunc 是小数去尾函数 —— Description By Shuchong
            if (j * j + tmp * tmp != i)
                continue;
            if ((gcd(j * j, tmp * tmp) == 1) && (j != tmp))
                ans++;
        }
        if (r / i != i) {
            for (long long j = 1; j * j <= 1ll * (i >> 1); j++) {
                long long tmp = 1ll * trunc(sqrt((r / i) - (j * j))); // trunc 是小数去尾函数 —— Description By Shuchong
                if (j * j + tmp * tmp != (r / i))
                    continue;
                if ((gcd(j * j, tmp * tmp) == 1) && (j != tmp))
                    ans++;
            }
        }
    }
    printf("%lld", 4 * (ans + 1));
    return 0;
}

别忘了是 $4$ 个坐标系和 $4$ 段轴，最后要加 $1$ 和 乘 $4$ 哦 ~

期望得分：$50$ 分
提交记录：Link

Solution 2

老是 $50$ 分我也很痛苦，Qiuly 巨佬跟我说让我看看 3B1B 的 Video 然后就可以找出做法了

以下为视频内容，故用 > 框起来

将 $r$ 质因数分解为

$$r=p_1^{a_1}\times p_2^{a_2}\times\cdots\times p_k^{a_k}$$

当 $p_i=4n+1$ 时，$ans$ 会乘上 $2k_1+1$

所以，我们直接把 $r$ 分解个质因数即可 ~

代码如下：

#include <bits/stdc++.h>

using namespace std;

int a[1000086];

int main () {
    int r;
    scanf("%d", &r);
    int cnt = 0;
    for (int i = 2; i <= sqrt(r); i++) {
        if (!a[i]) 
            a[++cnt] = i;
        for (int j = 1; j <= cnt; j++){
            if (a[j] * i > sqrt(r))
                break;
            a[a[j] * i] = 1;
            if (i % a[j] == 0)
                break;
        }
    }
    int ans = 1;
    for (int i = 1; i <= cnt; i++) {
        int tmp = 0;
        while (r % a[i] == 0) {
            tmp++;
            r /= a[i];
        }
        if ((a[i] - 1) % 4 == 0)
            ans *= (2 * tmp + 1);
    }
    if (r != 1 && (r - 1) % 4 == 0)
        ans *= 3;
    printf("%d", 4 * ans);
    return 0;
}

期望得分：$100$ 分
提交记录：Link

参考资料：

Solution 1：Wolfycz 大佬的 博客
Solution 2：3B1B 的 Video