直角三角形 题解

· · 个人记录

首先30pts暴力随便打

然后你需要知道勾股数组

对于70pts，你只需要O(n\log n)跑出本原勾股数组，然后做一个类似筛法的东西就可以求出答案了.

对于100pts，莫比乌斯反演

只需要枚举所有的本原勾股数组的s,t就好了.容易看出一个本原勾股数(s,t)的周长是s(s+t)，答案即

\sum\limits_{s,t}[s>t\geq 1][odd(s)][odd(t)][\gcd(s,t)=1]\left\lfloor\frac{n}{s(s+t)}\right\rfloor =\sum\limits_{s,t,d}[d=s+t][s>t\geq 1][even(d)][\gcd(s,d)=1]\left\lfloor\frac{n}{sd}\right\rfloor =\sum\limits_{s,d}[1<d<s<2d][\gcd(s,2d)=1]\left\lfloor\frac{n}{2sd}\right\rfloor =\sum\limits_{s,d,k}[1<d<s<2d][k\mid s][k\mid 2d]\mu(k)\left\lfloor\frac{n}{2sd}\right\rfloor =\sum\limits_{s,d,k}[1<d<s<2d][k\mid s][k\mid d][odd(k)]\mu(k)\left\lfloor\frac{n}{2sd}\right\rfloor+\sum\limits_{s,d,k}[1<d<s<2d][k\mid s][\frac{k}{2}\mid d][even(k)]\mu(k)\left\lfloor\frac{n}{2sd}\right\rfloor

接下来我们设odd(k)的部分和even(k)的部分分别为S_1和S_2

S_1=\sum\limits_{s,d,k}[1<d<s<2d][k\mid s][k\mid d][odd(k)]\mu(k)\left\lfloor\frac{n}{2sd}\right\rfloor =\sum\limits_{s,d,k}[1<d<s<2d][k\geq 1][(2k-1)\mid s][(2k-1)\mid d]\mu(2k-1)\left\lfloor\frac{n}{2sd}\right\rfloor =\sum\limits_{s,d,k}[1<d<s<2d][k\geq 1]\mu(2k-1)\left\lfloor\frac{n}{2sd(2k-1)^2}\right\rfloor

设t=\left\lfloor\frac{n}{2(2k-1)^2}\right\rfloor(这只是个重命名而已，不然底下式子太丑了)

=\sum\limits_{k=1}^{\sqrt{n}}\mu(2k-1)\sum\limits_{d=2}^t\sum\limits_{s=d+1}^{\min(2d-1,t/d)}\left\lfloor\frac{t}{sd}\right\rfloor

设S(n)=\sum\limits_{i=2}^n\sum\limits_{j=i+1}^{\min(2i-1,n/i)}\left\lfloor\frac{n}{ij}\right\rfloor

这个东西说实话没什么好的做法，大力枚举每一个i，然后数论分块算后面那个东西.因为当i>\sqrt{n}时后面那一坨就是0了，于是只需要枚举到\sqrt{n}，复杂度O(\sum\limits_{i=1}^{\sqrt{n}}\min(i,\sqrt{\frac{n}{i}}))=O(n^\frac{3}{4}).

然后答案就是\sum\limits_{k=1}^{\sqrt{n}}\mu(2k-1)S(t)，这东西也暴力算，复杂度

$k$是偶数那边基本一样写，最后的式子... 设$t=\left\lfloor\frac{n}{(2k)^2}\right\rfloor$，答案就是 $\sum\limits_{k=1}^{\sqrt{n}}\mu(2k)\sum\limits_{d=2}^t\sum\limits_{s=\frac{d}{2}+1}^{\min(d-1,t/d)}\left\lfloor\frac{t}{sd}\right\rfloor

然后和上面一样算.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
long long n;
int mu[500000],p[500000],prime[500000],cnt;
long long sqr(long long x){return x*x;}
long long S1(long long n)
{
    long long ans=0;
    for(int i=1;1ll*i*i<=n;i++)
    {
        long long tn=n/i;
        for(int j=i+1,lt;j<=(2*i-1)&&j<=tn;j=lt+1)
        {
            lt=min(tn/(tn/j),2*i-1LL);
            ans=(ans+(lt-j+1)*(tn/j));
        }
    }
    return ans;
}
void make(int n)
{
    mu[1]=p[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(!p[i])prime[++cnt]=i,mu[i]=-1;
        for(int j=1;j<=cnt&&i*prime[j]<=n;j++)
        {
            int x=i*prime[j];p[x]=1;
            if(i%prime[j])mu[x]=-mu[i];
            else break;
        }
    }
}
long long S2(long long n)
{
    long long ans=0;
    for(int i=1;1ll*i*i<=n*2;i++)
    {
        long long tn=n/i;
        for(int j=(i>>1)+1,lt;j<i&&j<=tn;j=lt+1)
        {
            lt=min(tn/(tn/j),i-1LL);
            ans=(ans+(lt-j+1)*(tn/j));
        }
    }
    return ans;
}
int main()
{
    scanf("%lld",&n);
    make(sqrt(n));long long ans=0;
    int lim1=(sqrt(n)+1)/2;
    for(int i=1;i<=lim1;i++)
        ans=(ans+mu[(i<<1)-1]*S1(n/(2*(sqr(2*i-1)))));  
    lim1=sqrt(n)/2;
    for(int i=1;i<=lim1;i++)
        ans=(ans+mu[i<<1]*S2(n/sqr(2*i)));
    cout<<ans<<endl;
}