J.杰哥的直角三角恋

题解

首先注意到任意一组勾股数 $a^{2} + b^{2} = c^{2}$ 可以表示为 $a = x^{2} - y^{2}$ ， $b = 2 x y$ ， $c = x^{2} + y^{2}$

那么问题可以转化成满足以下条件的 $(x, y)$ 点对的个数:

$x^2+y^2\leq n,x> y\geq 1$
$\gcd(x,y)=1$ （用反证法，若 $\gcd(x,y)=k>1$ ，那么设 $x = p k$ ， $y = q k$ 代入得 $a = (p^{2} - q^{2}) k^{2}$ ， $b = 2 p q k^{2}$ ， $c = (p^{2} + q^{2}) k^{2}$ ，显然不互素）
$x, y$ 奇偶性不同。(假如同为奇数则 $a$ ， $b$ ， $c$ 都为偶数，同为偶数则亦然）

当 $2x^2\leq n$ 时，此时 $y < x$ 。若 $x$ 是偶数，则此部分的贡献是 $\varphi(x)$ ；若 $x$ 是奇数，则此部分的贡献是 $\frac{\varphi(x)}{2}$ 。这一部分复杂度为 $\Theta( \sqrt{\frac{n}{2}})$ 。

当 $2x^2\leq n$ 时，此时 $y\leq \sqrt{n-x^2}$ ，所以就是求 $\sum_{x=\sqrt{n/2}+1}^{\sqrt{n}}\sum_{y=1}^{\sqrt{n-x^2}}[\gcd(x,y)=1]$

若 $x$ 是偶数

ans1=\sum_{x=\sqrt{n/2}+1,2\mid{x}}^{\sqrt{n}}\sum_{d\mid{x}}\mu(d)\frac{\sqrt{n-x^2}}{d}\\ =\sum_{d=1}^{\sqrt{n}}\mu(d)\sum_{k=(\sqrt{n/2}+1)/d}^{\frac{\sqrt{n}}{d}}\frac{\sqrt{n-k^2d^2}}{d}[2\mid{kd}]\\

若 $x$ 是奇数

ans2=\sum_{x=\sqrt{n/2}+1,2\nmid{x}}^{\sqrt{n}}\sum_{d\mid{x}}\mu(d)\frac{\sqrt{n-x^2}}{2d}\\ \sum_{d=1}^{\sqrt{n}}\mu(d)\sum_{k=(\sqrt{n/2}+1)/d}^{\frac{\sqrt{n}}{d}}\frac{\sqrt{n-k^2d^2}}{2d}[2\nmid{(kd)}]\\

复杂度大概是 $\mathcal O(\sqrt{n}\ln\sqrt{n})$ 。

std

#include<bits/stdc++.h>
using namespace std;
#define maxn 10000005
#define int long long
int mu[maxn];
int p[maxn];
int tot;
int v[maxn];
int phi[maxn];
void pre() {
    mu[1] = 1;
    phi[1]=1;
    for (int i = 2; i <= 1e7; ++i) {
        if (!v[i]) mu[i] = -1, p[++tot] = i,phi[i]=i-1;
        for (int j = 1; j <= tot && i <= 1e7 / p[j]; ++j) {
            v[i * p[j]] = 1;
            if (i % p[j] == 0) {
                mu[i * p[j]] = 0;
                phi[i*p[j]]=phi[i]*p[j];
                break;
            }
            else {
                phi[i*p[j]]=phi[i]*phi[p[j]];
                mu[i * p[j]] = -mu[i];
            }
        }
    }
}
signed main() {
    pre();
    int n;
    cin >> n;
    int m = (sqrt(n / 2));
    int mm = sqrt(n / 2) + 1;
    int mmm = sqrt(n);
    int ans = 0;
    for (int i = 2; i <= m; i++) {
        if (i % 2 == 0)ans += phi[i];
        else ans += phi[i] / 2;
    }
    for (int d = 1; d <= mmm; d++) {
        for (int k = mm / d; k <= mmm / d; k++) {
            if ((k * d) >= mm && (k * d) <= mmm && (k * d) % 2 == 0) {
                ans += mu[d] * ((int) sqrt(n - d * d * k * k) / (d));
            }
        }
    }
    for (int d = 1; d <= mmm; d++) {
        for (int k = mm / d; k <= mmm / d; k++) {
            if ((k * d) >= mm && (k * d) <= mmm && (k * d) % 2) {
                ans += mu[d] * ((int) sqrt(n - d * d * k * k) / 2 / d);
            }
        }
    }
    cout << ans << '\n';
}

题解 | #J.杰哥的直角三角恋#

J.杰哥的直角三角恋

题解

std