P3455 [POI2007]ZAP-Queries

╰半橙微兮° 2021-12-17 02:49 154阅读 0赞

[传送门][Link 1]

首先对于询问 $x,a,b$ 答案就是 $f\[x\]=\\sum\_\{i=1\}^\{a\}\\sum\_\{j=1\}^\{b\}\[gcd(i,j)==x\]$

看到 $gcd(i,j)$，莫比乌斯反演走起

设 $F\[x\]=\\sum\_\{i=1\}^\{a\}\\sum\_\{j=1\}^\{b\}\[x|gcd(i,j)\]$

那么有 $F\[x\]=\\sum\_\{x|d\}f\[d\]$ 且考虑 $F\[x\]$ 的意义发现 $F\[x\]=\\left \\lfloor \\frac\{a\}\{x\} \\right \\rfloor \\left \\lfloor \\frac\{b\}\{x\} \\right \\rfloor$

直接反演：$f\[x\]=\\sum\_\{x|d\}\\mu (d/x)F\[d\]=\\sum\_\{x|d\}\\mu (d/x)\\left \\lfloor \\frac\{a\}\{d\} \\right \\rfloor \\left \\lfloor \\frac\{b\}\{d\} \\right \\rfloor$

考虑枚举 $x$ 的倍数 $k$，那么：$f\[x\]=\\sum\_\{k\}\\mu(k)\\left \\lfloor \\frac\{a\}\{kx\} \\right \\rfloor\\left \\lfloor \\frac\{b\}\{kx\} \\right \\rfloor$

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

所以 $f\[x\]==\\sum\_\{k\}\\mu(k)\\left \\lfloor \\frac\{\\left \\lfloor \\frac\{a\}\{x\} \\right \\rfloor\}\{k\} \\right \\rfloor\\left \\lfloor \\frac\{\\left \\lfloor \\frac\{b\}\{x\} \\right \\rfloor\}\{k\} \\right \\rfloor$

然后直接数论分块就好了，单次询问复杂度 $O( \\sqrt (n) )$

总复杂度 $O(n \\sqrt (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=2e6+7,M=5e4;
    int Q,n,m,d,pri[N],mu[N],sum[N],tot;
    ll f[N],F[N],ans;
    bool not_pri[N];
    void pre()
    {
        not_pri[1]=1; mu[1]=1;
        for(int i=2;i<=M;i++)
        {
            if(!not_pri[i]) pri[++tot]=i,mu[i]=-1;
            for(int j=1;j<=tot;j++)
            {
                ll t=1ll*i*pri[j]; if(t>M) break;
                not_pri[t]=1; if(!(i%pri[j])) break;
                mu[t]=-mu[i];
            }
        }
        for(int i=1;i<=M;i++) sum[i]=sum[i-1]+mu[i];
    }
    int main()
    {
        Q=read(); pre();
        while(Q--)
        {
            n=read(),m=read(),d=read();
            n/=d; m/=d; int mx=min(n,m); ans=0;
            for(int l=1,r=0;l<=mx;l=r+1)
            {
                r=min(mx, min(n/(n/l),m/(m/l)) );
                ans+=1ll*(sum[r]-sum[l-1])*(n/l)*(m/l);
            }
            printf("%lld\n",ans);
        }
        return 0;
    }

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

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