P2568 GCD

骑猪看日落 2021-12-10 02:53 235阅读 0赞

[传送门][Link 1]

设 $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;
    }

转载于:https://www.cnblogs.com/LLTYYC/p/11136444.html

[Link 1]: https://www.luogu.org/problemnew/show/P2568