P2568 GCD-蒲公英云

P2568 GCD

传送门

设 $f[x]=\sum_i^N\sum_j^N[gcd(i,j)==x]$

那么答案就是 $Ans=\sum_{prime}f(prime)$

显然 $f$ 可以反演，设 $F[x]=\sum_i^N\sum_j^N[x|gcd(i,j)]$

那么 $F[x]=\sum_{x|d}f[d]$，并且容易得到 $F[x]=\left \lfloor \frac{N}{x} \right \rfloor \left \lfloor \frac{N}{x} \right \rfloor$

直接反演得到 $f[x]=\sum_{x|d}\mu(d/x)F[d]=\sum_{x|d}\mu(d/x)\left \lfloor \frac{N}{x} \right \rfloor \left \lfloor \frac{N}{x} \right \rfloor$

枚举 $x$ 的倍数 $k$，得到 $f[x]=\sum_k\mu(k)\left \lfloor \frac{N}{kx} \right \rfloor \left \lfloor \frac{N}{kx} \right \rfloor$

因为 $\left \lfloor \frac{N}{kx} \right \rfloor=\left \lfloor \frac{\left \lfloor \frac{N}{x} \right \rfloor}{k} \right \rfloor$

所以 $f[x]==\sum_k\mu(k)\left \lfloor \frac{\left \lfloor \frac{N}{x} \right \rfloor}{k} \right \rfloor\left \lfloor \frac{\left \lfloor \frac{N}{x} \right \rfloor}{k} \right \rfloor$

可以数论分块，然后枚举质数 $p$ 并把所有的 $f[p]$ 加起来就是答案了

质数约有 $sqrt(n)$ 个，单次求 $f$ 复杂度 $sqrt(n)$，总复杂度 $O(n)$

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
typedef long long ll;
inline int read()
{
    int x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
    while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
    return x*f;
}
const int N=2e7+7;
int n,pri[N],mu[N],tot;
bool not_pri[N];
ll ans;
void pre()
{
    mu[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(!not_pri[i]) pri[++tot]=i,mu[i]=-1;
        for(int j=1;j<=tot;j++)
        {
            ll g=1ll*i*pri[j]; if(g>n) break;
            not_pri[g]=1; if(!(i%pri[j])) break;
            mu[g]=-mu[i];
        }
    }
    for(int i=2;i<=n;i++) mu[i]+=mu[i-1];
}
int main()
{
    n=read(); pre();
    for(int i=1;i<=tot;i++)
    {
        int p=pri[i],m=n/p;
        for(int l=1,r;l<=m;l=r+1)
        {
            r=m/(m/l);
            ans+=1ll*(mu[r]-mu[l-1])*(m/l)*(m/l);
        }
    }
    printf("%lld\n",ans);
    return 0;
}