J.杰哥的直角三角恋

题解

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

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

1. $x^2+y^2\le n,x>y\ge 1x^2+y^2\backslash leq\; n,x>\; y\backslash geq\; 1$

2. $\gcd (x,y)=1\backslash gcd(x,y)=1$ （用反证法，若 $\gcd (x,y)=k>1\backslash gcd(x,y)=k>1$ ，那么设 $x=pkx=pk$ ，$y=qky=qk$ 代入得 $a=(p^2-q^2)k^{2}a=(p^2-q^2)k^2$ ， $b=2pq{k}^{2}b=2pqk^2$ ，$c=(p^2+q^2)k^{2}c=(p^2+q^2)k^2$ ，显然不互素）

3. $x,yx,y$ 奇偶性不同。(假如同为奇数则 $aa$ ，$bb$ ，$cc$ 都为偶数，同为偶数则亦然）

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

当 $2x^2\le n2x^2\backslash leq\; n$ 时，此时 $y\le \sqrt{n-x^2}y\backslash leq\; \backslash sqrt\{n-x^2\}$ ，所以就是求 ${\sum }_{x=\sqrt{n\mathrm{/}2}+1}^{\sqrt{n}}{\sum }_{y=1}^{\sqrt{n-x^2}}[\gcd (x,y)=1]\backslash sum\_\{x=\backslash sqrt\{n/2\}+1\}^\{\backslash sqrt\{n\}\}\backslash sum\_\{y=1\}^\{\backslash sqrt\{n-x^2\}\}[\backslash gcd(x,y)=1]$

1. 若$xx$是偶数

2. 若 $xx$ 是奇数

复杂度大概是 $\mathcal{O}(\sqrt{n}\ln \sqrt{n})\backslash mathcal\; O(\backslash sqrt\{n\}\backslash ln\backslash 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';
}