莫比乌斯反演

线性筛莫比乌斯函数

int ss[N+5],mu[N+5],cnt,sum[N+5]; 
bool vs[N+5];
il void init(int n){
    for(ri unsigned int i=2;i<=n;++i){
        if(!vs[i]) ss[++cnt]=i,mu[i]=-1;
        for(ri unsigned int j=1;j<=cnt&&i*ss[j]<=n;++j){
            vs[i*ss[j]]=1;
            if(i%ss[j]==0) break;
            mu[i*ss[j]]=-mu[i];
        }
    }
    return;
}

算一个数的莫比乌斯函数

il int mu(int n){
    int res=n,as=1;
    for(ri int i=2;i*i<=res;++i){
        if(res%i==0){
            res/=i;
            if(res%i==0) return 0;
            as=-as;
        }
    }
    if(res>1) as=-as;
    return as;
}

数论分块

il int sol(int n,int m){
    int as=0;
    for(ri int l=1,r=0;l<=n;l=r+1){
        r=min(n/(n/l),m/(m/l));
        as+=(sum[r]-sum[l-1])*(n/l)*(m/l);
    }  
    retrun as;
}

常用trick

将上式 \({n}\) 替换成\({gcd(i,j)}\)可推得

于是可以得到

把\(d\)提到前面，可得

这样就可用线性筛加数论分块\(O(n+Q\cdot\sqrt{n})\)求解啦~

反演

• \[\text{若有}f(n)=\sum_{d\mid n}g(d)\text{，则有}g(n)=\sum_{ d\mid n}μ(d)\cdot f({\frac{n}{d}}) \]

• \[\text{若有}f(n)=\sum_{{n\mid d}}g(d)\text{，则有}g(n)=\sum_{n\mid d} μ({\frac{d}{n}})\cdot f(d) \]

其他式子

\(\Large\text{狄利克雷卷积}\)

• \(\Large\text{定义}\)

1. 对于两个数论函数\(f(x)\)和\(g(x)\),则它们的狄利克雷卷积得到的结果\(h(x)\)定义为：\(h(x)=\sum_{d\mid x}f(d)\cdot g(\frac{x}{d})=\sum_{a\cdot b}f(a)\cdot g(b)\),简记为\(h=f* g\)

2. 单位函数\(\epsilon:\epsilon(n)=\lbrack n=1\rbrack,\)

3. 幂函数\(id:id_{k}(n)=n^k\)

4. 常数函数\(I:I(n)=1,\)

5. 恒等函数\(id:id(n)=n=id_1(n)\)

6. 对于所有的数论函数\(f(n)\)，均有\(f(n) * I(n)=I(n) * f(n)=f(n)\)

7. 积性函数逆元：\(f * g=\epsilon\)，称\(f,g\)互为逆元，记\(f=g^{-1}\)，逆元是唯一的

• \(\Large\text{性质}\)

1. 交换律:设\(f，g\)为任意二个数论函数，则\(f * g=g * f\)

2. 结合律:设\(f，g，h\)为任意三个数论函数，则\((f * g) * h = f * (g * h)\)

3. 分配律:\((f+g)* h=f* h+g* h\)

4. 等式的性质:\(f=g\)的充要条件是\(f* h=g* h，\)其中数论函数\(h(x)\)要满足\(h(1)\ne 0\)

• \(\Large\text{一些结论}\)

1. 两个积性函数的 \(Dirichlet\) 卷积也是积性函数

2. 积性函数的逆元也是积性函数

\(\Large\text{关于莫反}\)

1. \(\mu* I=\epsilon\)

2. \(I=\mu^{-1}\)

3. \(\varphi=\mu* id，\varphi* I=id\)

4. \(\varphi(n)= \sum_{d\mid n}d \cdot \mu(\frac{n}{d})\)

资料

OvO~

一些练习

\(\large\text{1.树林里的树 Trees in a Wood.}\)

原题链接

题目大意

求\(\frac{\sum_{i=-a}^{a}\sum_{j=-b}^{b}\lbrack\lvert gcd(i,j)\rvert=1\rbrack}{(2a+1)(2b+1)-1}(a\le 2000，b\le 2\times 10^6)\)，结果保留7位小数

推式子

一道非常基础的莫反题

可以发现4个象限对答案的贡献是一样的，考虑只处理第一象限，最后将答案乘4，再加上坐标轴上的4个点，注意总点数是(2a+1)(2b+1)-1（原点不算在内）

第一象限的贡献为

可以发现是一个典型莫反的式子，按照套路

考虑枚举d

不难发现

于是

当\(l\le a,b\le r\)时，\(\lfloor\frac{a}{d}\rfloor\cdot\lfloor\frac{b}{d}\rfloor\)的值不变，考虑将其提取出来，乘\(\sum_{d=l}^r\mu(d)\)
令\(sum[d]=\sum_{i=1}^d\mu(i)\)，则\(\sum_{d=l}^r\mu(d)=sum[r]-sum[l-1]\)可以\(O[1]\)得到
考虑数论分块，因为\(\lfloor\frac{n}{d}\rfloor\)只有\(\lfloor\sqrt{n}\rfloor\)种取值，所以在预处理出\(sum[i]\)的情况下，可以\(O(\sqrt{n})\)求出\(s\)

接下来考虑如何预处理\(sum\)
由\(\mu\)函数的定义可知其为积性函数，可以用欧拉筛\(O(n)\)筛出（杜教筛更优，但是我不会），那么就可以\(O(n)\)预处理出\(\mu\)的前缀和\(sum\)

总复杂度为\(O(n+Q\cdot\sqrt{n})\)，可以通过此题~

#include<bits/stdc++.h>
#define il inline
#define cs const
#define ri register
#define int long long
using namespace std;
namespace Q{
    il int rd(){
        ri int x=0,f=1;ri char c=getchar();
        while(c<'0'||c>'9') f=(c=='-')?-1:1,c=getchar();
        while(c>='0'&&c<='9') x=x*10+(c^48),c=getchar();
        return x*f; 
    }
    cs int N=2000;
    int mu[N+5],ss[N+5],cnt,sum[N+5];
    bool vs[N+5];
    il void init(){
        mu[1]=1,sum[1]=1;
        for(ri int i=2;i<=N;++i){
            if(!vs[i]) ss[++cnt]=i,mu[i]=-1;
            for(ri int j=1;j<=cnt&&ss[j]*i<=N;++j){
                vs[i*ss[j]]=1;
                if(i%ss[j]==0) break;
                mu[i*ss[j]]=-mu[i];
            }
            sum[i]=sum[i-1]+mu[i];
        }
    }
    il void done(int n,int m){
        if(n>m) swap(n,m);
        double as=0;
        for(ri int l=1,r=0;l<=n;l=r+1){
            r=min(n/(n/l),m/(m/l));
            as+=(sum[r]-sum[l-1])*(n/l)*(m/l);
        }
        as=as*4+4;
        as=as/((n*2+1)*(m*2+1)-1);
        printf("%.7lf\n",as);
        return;
    }
}
using namespace Q;
signed main(){
    init();
    int a=rd(),b=rd();
    while(a||b){
        done(a,b);
        a=rd(),b=rd();
    }	
    return 0;
} 

\(\large\text{2.P2257 YY的GCD}\)

原题链接

题目大意

求\(\sum_{i=1}^n\sum_{j=1}^m\lbrack gcd(i,j)\in prime\rbrack (n,m\le 10^7)\)

推式子

考虑枚举质数

这样就跟上一题差不多了

枚举\(d\)

一个常用套路，令\(T=p\cdot d\)，枚举\(T\)

发现\(\displaystyle\sum_{p|T,p\in prime}\mu(\frac{T}{p})\)可以预处理
令\(f(T)=\displaystyle\sum_{p|T,p\in prime}\mu(\frac{T}{p})\)对于每一个质数\(p\)，枚举\(d\)，将\(f(d\cdot p)\)加上\(\mu(d)\)，第二维循环是一个调和级数，预处理总复杂度约为\(n\cdot ln(n)\)
预处理出\(f(T)\)的前缀和，然后就可以用数论分块\(O(\sqrt n)\)求出\(s\)
总复杂度约为\(O(n\cdot ln(n)+Q\cdot\sqrt n)\)，可过~
\(ps：f(T)\)可以\(O(n)\)线性筛出来

il void init(int n){
    mu[1]=1;
    for(ri int i=2;i<=n;++i){
        if(!vs[i]) ss[++cnt]=i,mu[i]=-1,f[i]=1;
        for(ri int j=1;j<=tot&&ss[j]*i<=n;++j){
            vs[i*ss[j]]=1;
            if(i%ss[j]){
                f[i*ss[j]]=-f[i]+mu[i];
                mu[i*ss[j]]=-mu[i];
            }
            else{
                f[i*ss[j]]=mu[i];
                break;
            }
        }
        sum[i]=sum[i-1]+f[i];
    }
    return;
} 

#include<bits/stdc++.h>
#define il inline
#define cs const
#define ri register
using namespace std;
il int rd(int &x){
    x=0;ri int f=1;ri char c=getchar();
    while(c<'0'||c>'9') f=(c=='-')?-1:1,c=getchar();
    while(c>='0'&&c<='9') x=x*10+(c^48),c=getchar();
    return x*f;
}
il void wt(long long x){
    if(x<0) x=-x,putchar('-');
    ri unsigned short a[15]={0},tl=0;
    do{a[++tl]=x%10,x/=10;}while(x);
    for(ri int i=tl;i;--i) putchar(a[i]+48);
}
cs int N=1e7;
long long sum[N+5];
int ss[N+5],mu[N+5],cnt,f[N+5];
bool vs[N+5];
il void init(int n){
    mu[1]=1;
    for(ri unsigned int i=2;i<=n;++i){
        if(!vs[i]) ss[++cnt]=i,mu[i]=-1;
        for(ri unsigned int j=1;j<=cnt&&i*ss[j]<=n;++j){
            vs[i*ss[j]]=1;
            if(i%ss[j]==0) break;
            mu[i*ss[j]]=-mu[i];
        }
    }
    for(ri unsigned int j=1;j<=cnt;++j){
        for(ri int i=1;ss[j]*i<=n;++i){
            f[i*ss[j]]+=mu[i];
        }
    }
    for(ri unsigned int i=1;i<=n;++i){
        sum[i]=sum[i-1]+1ll*f[i];
    }
}
signed main(){
    int t=0,n=0,m=0;rd(t);
    ri long long as=0;init(N);
    while(t--){
        rd(n),rd(m),as=0;
        if(m<n) swap(m,n);
        for(ri unsigned int l=1,r=0;l<=n;l=r+1){
            r=min((n/l)?n/(n/l):n,(m/l)?m/(m/l):m);
            as+=1ll*(n/l)*(m/l)*(sum[r]-sum[l-1]);
        }
        wt(as),putchar('\n');
    }
    return 0;
}

\(\large\text{3.P2398 GCD SUM}\)
原题链接

\(\large\text{4.P4450 双亲数}\)
原题链接

\(\large\text{5.P3455 [POI2007]ZAP-Queries}\)
原题链接

\(\large\text{6.P2522 [HAOI2011]Problem b}\)
原题链接

\(\large\text{7.P2231 [HNOI2002]跳蚤}\)
原题链接

\(\large\text{8.P1390 公约数的和}\)
原题链接

\(\large\text{9.P6810 「MCOI-02」Convex Hull 凸包}\)
原题链接

\(\large\text{10.Array Equalizer}\)
原题链接

\(\large\text{11.LCMSUM - LCM Sum}\)