bzoj2301:[HAOI2011]Problem b(莫比乌斯反演)

Author Avatar
Sakits 4月 04, 2018

题解

  莫反裸题…
  显然一个询问可以拆成四个,用类似二维前缀和的方法得到答案,也就是问题转化成了求:

i=1nj=1m[(i,j)=k]\sum_{i=1}^n\sum_{j=1}^m[(i,j)=k]

  令n=nkn=\left \lfloor \frac{n}{k} \right \rfloorm=mkm=\left \lfloor \frac{m}{k} \right \rfloor,问题转化为求:

i=1nj=1m[(i,j)=1]\sum_{i=1}^{n}\sum_{j=1}^{m}[(i,j)=1]

  令F(i)F(i)i(x,y)i|(x,y)的个数,显然有:

F(i)=nimiF(i)=\left \lfloor \frac{n}{i} \right \rfloor\left \lfloor \frac{m}{i} \right \rfloor

  令f(i)f(i)为由(x,y)=i(x,y)=i的个数,莫比乌斯反演定理可得:

f(i)=idμ(di)F(d)=idμ(di)ndmd=ndmdidμ(di)\begin{aligned} f(i)&=\sum_{i|d}\mu(\frac{d}{i})F(d)\\ &=\sum_{i|d}\mu(\frac{d}{i})\left \lfloor \frac{n}{d} \right \rfloor\left \lfloor \frac{m}{d} \right \rfloor\\ &=\left \lfloor \frac{n}{d} \right \rfloor\left \lfloor \frac{m}{d} \right \rfloor\sum_{i|d}\mu(\frac{d}{i}) \end{aligned}

  左半部分取值最多只有2(n+m)2(\sqrt{n}+\sqrt{m})种,右半部分维护莫比乌斯函数的前缀和即可求得上式的值,复杂度O(nn)O(n\sqrt{n})

代码

#include<iostream> 
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath> 
#include<algorithm> 
#define ll long long
using namespace std;
const int maxn=500010, inf=1e9;
int T, n, a, b, c, d, k, cntp;
int pri[maxn], mu[maxn];
ll sum[maxn];
bool v[maxn];
inline void read(int &k)
{
    int f=1; k=0; char c=getchar();
    while(c<'0' || c>'9') c=='-'&&(f=-1), c=getchar();
    while(c<='9' && c>='0') k=k*10+c-'0', c=getchar();
    k*=f;
}
inline void getmu(int n)
{
    mu[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(!v[i]) mu[i]=-1, pri[++cntp]=i;
        for(int j=1;pri[j]*i<=n;j++)
        {
            v[pri[j]*i]=1;
            if(i%pri[j]==0)
            {
                mu[pri[j]*i]=0; 
                break;
            }
            mu[pri[j]*i]=-mu[i];
        }
    }
    for(int i=1;i<=n;i++) sum[i]=sum[i-1]+mu[i];
}
inline ll getans(int n, int m)
{
    ll ans=0;
    if(n>m) swap(n, m);
    for(int i=1, last;i<=n;i=last+1)
    {
        last=min(n/(n/i), m/(m/i));
        ans+=1ll*(n/i)*(m/i)*(sum[last]-sum[i-1]);
    }
    return ans;
}
int main()
{
    getmu(50000); read(T);
    while(T--)
    {
        read(a); read(b); read(c); read(d); read(k);
        a--; c--; a/=k; b/=k; c/=k; d/=k;
        printf("%lld\n", getans(b, d)-getans(a, d)-getans(b, c)+getans(a, c));  
    }
}