首页 > 其他分享 >莫比乌斯反演

莫比乌斯反演

时间：2022-10-24 16:15:43浏览次数：66  
标签：lfloor frac cdot 乌斯 sum rfloor mu 反演 莫比

线性筛莫比乌斯函数

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

\[\sum_{d \mid n}μ(d)=[d=1] \]

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

\[\sum_{d \mid gcd(i,j)}μ(d)=[gcd(i,j)] \]

于是可以得到

\[\sum_{i=1}^{n}\sum_{j=1}^{m}gcd(i,j)=\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{d \mid gcd(i,j)}\mu(d) \]

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

\[\sum_{i=1}^{n}\sum_{j=1}^{m}gcd(i,j) =\sum_{d=1}^{n}μ(d)\cdot\sum_{i}^{\lfloor\frac{n}{d}\rfloor}1\cdot\sum_{j}^{\lfloor\frac{m}{d}\rfloor}1 =\sum_{d=1}^{n}μ(d)\cdot\lfloor\frac{n}{d}\rfloor\cdot\lfloor\frac{m}{d}\rfloor\]

这样就可用线性筛加数论分块\(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（原点不算在内）

第一象限的贡献为

\[s=\sum_{i=1}^a\sum_{j=1}^b[gcd(i,j)=1] \]

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

\[s=\sum_{i=1}^a\sum_{j=1}^b\sum_{d|gcd(i,j)}\mu(d) \]

考虑枚举d

\[s=\sum_{d=1}^a\mu(d)\cdot\sum_{i=1}^{\lfloor\frac{a}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{b}{d}\rfloor}1 \]

不难发现

\[\sum_{i=1}^{\lfloor\frac{a}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{b}{d}\rfloor}1=\lfloor\frac{a}{d}\rfloor\cdot\lfloor\frac{b}{d}\rfloor \]

于是

\[s=\sum_{d=1}^a\mu(d)\cdot \lfloor\frac{a}{d}\rfloor\cdot\lfloor\frac{b}{d}\rfloor\]

当\(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)\)

推式子

考虑枚举质数

\[s=\sum_{p\le n,p\in prime}\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{p}\rfloor}\lbrack gcd(i,j)=1\rbrack \]

这样就跟上一题差不多了

\[s=\sum_{p\le n,p\in prime}\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{p}\rfloor}\sum_{d|gcd(i,j)}\mu(d) \]

枚举\(d\)

\[s=\sum_{p\le n,p\in prime}\sum_{d=1}^{\lfloor\frac{n}{p}\rfloor}\mu(d)\cdot\sum_{i=1}^{\lfloor\frac{n}{p\cdot d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{p\cdot d}\rfloor}1 \]

\[s=\sum_{p\le n,p\in prime}\sum_{d=1}^{\lfloor\frac{n}{p}\rfloor}\mu(d)\cdot\lfloor\frac{n}{p\cdot d}\rfloor\cdot\lfloor\frac{m}{p\cdot d}\rfloor \]

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

\[s=\sum_{T=1}^{n}\lfloor\frac{n}{T}\rfloor\cdot\lfloor\frac{m}{T}\rfloor\cdot\sum_{p|T,p\in prime}\mu(\frac{T}{p}) \]

发现\(\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)\)线性筛出来

\[ f(i\cdot p)=\begin{cases} \mu(1) & i=1\\ \mu(i) &i\mod p=0\\ -f(i)+\mu(i) &i\mod p\ne 0 \end{cases}\]

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}\)

标签：lfloor,frac,cdot,乌斯,sum,rfloor,mu,反演,莫比
From： https://www.cnblogs.com/314159x/p/16820501.html

相关文章

  • 拉格朗日反演推导扩展Cayley公式
    萌新初学拉格朗日反演，这个看起来很对所以应该是对的吧？把\(n\)个点连成有\(k\)棵树的森林，并且要求\(1,2,\cdots,k\)这\(k\)个点两两不在同一棵树的方案数。首先......
  • bzoj 2301: [HAOI2011]Problem b mobius反演 RE
    ​​http://www.lydsy.com/JudgeOnline/problem.php?id=2301​​设f(i)为在区间[1,n]和区间[1,m]中，gcd(x,y)=i的个数。设F(i)为在区间[1,n]和区间[1,m]中，gcd(x,y)%......
  • 【Coel.学习笔记】莫比乌斯反演
    闲话记得在差不多一年前写扩展欧拉定理的时候我提了一句这周终于把古代猪文搞定了，数论这块的内容就只剩个博弈论了别提莫比乌斯反演之类的东西，我不想搞甚至刚开始写......
  • 莫比乌斯
    莫比乌斯函数定义\[\mu(n)=\begin{cases}1&n=1\\0&n含有平方因子\\(-1)^k&k为本质不同的质因子个数\end{cases}\]性质莫比乌斯函数是积性函数，且......
  • 算法学习笔记（数学）：数论分块 + 容斥原理 + 莫比乌斯函数
    算法学习笔记（数学）：数论分块+容斥原理+莫比乌斯函数这篇文章主要是要讲一道题目（链接在这里)以及梳理一下数论分块，莫比乌斯函数，容斥原理这些知识。先介绍下知识点吧qwq......
  • luogu P5518 幽灵乐团 / 莫比乌斯反演基础练习题
    重新学习了一下莫比乌斯反演，再来写一次这道题。Part1\[\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^C\dfrac{\text{lcm}(i,j)}{\gcd(i,k)}\]\[=\prod_{i=1}^A\prod_{j=1}^B......
  • AGC038C LCMs 详解（莫比乌斯反演好题）
    ProblemAGC038C给定一个长为\(n\)的序列\(A_1,A_2,\cdots,A_n\)，求\(\sum_{i=1}^{n}{\sum_{j=i+1}^{n}{lcm(A_i,A_j)}}\bmod998244353\)\(n\leq2\times10^5,A_i......
  • 容斥与反演技巧（一）
    二项式反演我们直接上式子好了一般有两种形式，第一种是\[f(n)=\sum_{i=0}^n\binom{n}{i}g(i)\iffg(n)=\sum_{i=0}^n(-1)^{n-i}\binom{n}{i}f(i)\]第二种是\[f(n)=\sum......
  • 【瞎口胡】单位根反演
    单位根反演是用单位根来表示整除关系的东西。定义式\[\left[k\midn\right]=\dfrac{1}{k}\sum\limits_{i=0}^{k-1}\omega_k^{in}\]如果\(k\midn\)，那么\(\omeg......
  • 莫比乌斯函数与莫比乌斯反演
    莫比乌斯函数很简单，莫比乌斯函数\(\mu(n)=\begin{cases}0&n有平方质因子\\1&n=1\\(-1)^k&k为本质不同质因子数量\end{cases}\)莫比乌斯函数可以用来做容......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99