BZOJ2301/LG2522 「HAOI2011」Problem B 莫比乌斯反演数论分块

问题描述

BZOJ2301

LG2522

积性函数

若函数 \(f(x)\) 满足对于任意两个最大公约数为 \(1\) 的数 \(m,n\) ，有 \(f(mn)=f(m) \times f(n)\)，则称 \(f(x)\) 为积性函数。

狄利克雷卷积和莫比乌斯函数

今天 zzk 神仙讲了一下狄利克雷卷积、数论分块和莫比乌斯反演。

几个数论函数

\[1(x)=1\]

\[id(x)=x\]

\[id^k(x)=x^k\]

\[\varepsilon(x)=\begin{cases}1&x=1\\0&x\neq1\end{cases}\]

以上这几个数论函数都是积性函数。

狄利克雷卷积

有函数 \(f(x),g(x)\) ，若有函数 \(h(x)=\sum\limits_{d|x}{f(d)g(\frac{x}{d})}\) ，则称 \(h(x)\) 是 \(f(x),g(x)\) 的卷积。

记作 \(h(x)=f(x)*g(x)\)

狄利克雷卷积有如下性质：

交换律，即 \(f*g=g*f\)
结合律，即 \((a*b)*c=a*(b*c)\)
若 \(f,g\) 都是积性函数，则 \(f*g\) 也是积性函数，即 \(f*g(mn)=f*g(m) \times f*g(n)((n,m)=1)\)

单位元 \(\varepsilon\)

若 \(f*g = \varepsilon\) ，则 \(f\) 与 \(g\) 互为逆

莫比乌斯函数

\(\mu(x)\)代表莫比乌斯函数。

对 \(x\) 应有质数唯一分解定理，将 \(x\) 表示为 \(x=\prod_{i=1}^{k} p_i^{c_i}\) ，则有

\[\mu(x)=\begin{cases}0&\exists c_i \ge 2\\(-1)^{k}&\forall c_i=1\end{cases}\]

莫比乌斯函数是一个积性函数，即对于满足 \((x,y)=1\) 的 \(x,y\) ，有 \(\mu(xy)=\mu(x) \times \mu(y)\)

有重要性质 \(\sum\limits_{d|x}{\mu(d)}=\varepsilon=\begin{cases}0&x \neq 1\\1&x=1\end{cases}\)

莫比乌斯反演

套式子：

\[f(x)=\sum\limits_{d|x}g(d) \Rightarrow g(x)=\sum\limits_{d|x}f(d)\mu(\frac{x}{d})\]

用狄利克雷卷积来解释，就是 \(f=g*1,g=f*\mu\)

数论分块

简单问题

数论分块一般的问题是求 \(\sum_{d=1}^n{\lfloor \frac{n}{d} \rfloor}\)

考虑分块思想，把 \(\lfloor \frac{n}{d} \rfloor\) 数值相同的划分为一块求。

于是可以得到以下代码：

稍复杂问题 \(1\)

题解

题意是要求 \(\sum\limits_{i=a}^{b}{\sum\limits_{j=c}^{d}{[(i,j)==k]}}\)

显然可以通过差分，将问题转化为求 \(\sum\limits_{i=1}^{n}{\sum\limits_{j=1}^{m}{[(i,j)==k]}}\)

可以通过在两边同时除去 \(k\) ，得到

\[\sum\limits_{i=1}^{\frac{n}{k}}{\sum\limits_{j=1}^{\frac{m}{k}}{[(i,j)==1]}}\]

考虑最大公约数为 \(1\) 的要求，可以想到 \([(i,j)==1]\) 的条件可以直接改为 \(\varepsilon((i,j))\)

又因为 \(\varepsilon((i,j))=\sum\limits_{d|(i,j)}{\mu(d)}\) ，所以式子转化为

\[\sum\limits_{i=1}^{\frac{n}{k}}{\sum\limits_{j=1}^{\frac{m}{k}}{\sum\limits_{d|(i,j)}{\mu(d)}}}\]

对 \(\sum\) 进行变换，得到

\(\mathrm{Code}\)

#include<bits/stdc++.h>
using namespace std;

const int maxn=50000;

int T;

void Init(void){
    scanf("%d",&T);
}

int p[maxn+7],pr[maxn+7],miu[maxn+7],s[maxn+7];
int tot;

void preprocess(){
    miu[1]=1;
    for(int i=2;i<=maxn;i++){
        if(!p[i]) p[i]=i,pr[++tot]=i,miu[i]=-1;
        for(int j=1;j<=tot;j++){
            if(i*pr[j]>maxn||p[i]<pr[j]) break;
            p[i*pr[j]]=pr[j];
            if(i%pr[j]) miu[i*pr[j]]=-miu[i];
            else miu[i*pr[j]]=0;
        }
    }
    for(int i=1;i<=maxn;i++) s[i]=s[i-1]+miu[i];
}

int calc(int x,int y){
    if(x>y) swap(x,y);
    if(x==0||y==0) return 0;
    int res(0);
    for(int l=1,r;l<=x;l=r+1){
        r=min(x/(x/l),y/(y/l));
        res+=(s[r]-s[l-1])*(x/l)*(y/l);
    }
    return res;
}


void Work(void){
    preprocess();
    while(T--){
        int a,b,c,d,k;
        scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
        --a,--c;
        printf("%d\n",calc(b/k,d/k)+calc(a/k,c/k)-calc(a/k,d/k)-calc(b/k,c/k));
    }
}

int main(){
    Init();
    Work();
    return 0;
}