专栏首页CSDN旧文数学--数论--莫比乌斯反演

数学--数论--莫比乌斯反演

一、莫比乌斯反演涉及知识 1.莫比乌斯函数 2.莫比乌斯的线性筛法 3.狄利克雷卷积 4.莫比乌斯反演详解 5.整除法分块 6.杜教筛

二、μ 莫比乌斯函数定义

μ ( n ) = { 1 n=1 ( − 1 ) k n= P1*P2*P3*...*Pk(其中P是质数) 0 else其他情况 μ(n)=\begin{cases} 1& \text{n=1}\\ (-1)^k& \text{n= P1*P2*P3*...*Pk(其中P是质数)}\\ 0& \text{else其他情况} \end{cases} μ(n)=⎩⎪⎨⎪⎧​1(−1)k0​n=1n= P1*P2*P3*...*Pk(其中P是质数)else其他情况​

也就是说如果n有平方质因子的话就为0。

三、莫比乌斯线性筛

int  prime[MAXN],prime_tot;
bool isprime[MAXN];
int mu[MAXN];
void pre_calc(int  limt)
{
    mu[1]=1;
    for(int i=2;i<=limt;i++)
    {
        if(!isprime[i]){
            prime[prime_tot]=i;
            mu[i]=-1;
        }
        for (int j=1;j<prime_tot;j++)
        {
            if(i*prime[j]>lim) break;
            isprime[i*prime[j]]= ture;
            if(i %prime[j]==0) {
                mu[i*prime[j]]=0;
                break;
            }else{
                mu[i*prime[j]]=-mu[i];
            }
        }
    }
}

四、狄利克雷卷积 (f*g)(n)= ∑ d ∣ n f ( d ) g ( n d ) \sum_{d|n}f(d)g( \frac{n}{d}) ∑d∣n​f(d)g(dn​)

积性函数指对于所有互质的整数a和b有性质f(a*b)=f(a)f(b)的数论函数。 完全积性函数不需要互质既有f(ab)=f(a) * f(b)

欧 拉 函 数 φ ( n ) 莫 比 乌 斯 函 数 , 关 于 非 平 方 数 的 质 因 子 数 目 μ ( n ) 最 大 公 因 子 , 当 k 固 定 的 情 况 g c d ( n , k ) 单 位 函 数 I d ( n ) = n 不 变 函 数 1 ( n ) = n 因 子 数 目 d ( n ) d = 1 ∗ 1 因 子 之 和 函 数 σ ( n ) σ = 1 ∗ I d 因 子 函 数 σ k ( n ) 幂 函 数 I d k ( n ) = n k 狄 利 克 雷 卷 积 单 位 元 ε = [ n = = 1 ]       当 n = 1 时 ε = 1 其 他 等 于 0 刘 维 尔 函 数 λ ( n ) 关 于 能 整 除 n 的 质 因 子 的 数 目 欧拉函数 φ(n) \\ 莫比乌斯函数,关于非平方数的质因子数目μ(n) \\ 最大公因子,当k固定的情况 gcd(n,k) \\ 单位函数Id(n)=n\\ 不变函数 1(n) =n\\ 因子数目 d(n) d=1*1\\ 因子之和函数σ(n) σ=1*Id\\ 因子函数 σk(n) \\ 幂函数Idk(n)=n^k\\ 狄利克雷卷积单位元ε=[n==1]\ \ \ \ \ 当n=1时ε=1其他等于0 \\ 刘维尔函数 λ(n) 关于能整除n的质因子的数目 欧拉函数φ(n)莫比乌斯函数,关于非平方数的质因子数目μ(n)最大公因子,当k固定的情况gcd(n,k)单位函数Id(n)=n不变函数1(n)=n因子数目d(n)d=1∗1因子之和函数σ(n)σ=1∗Id因子函数σk(n)幂函数Idk(n)=nk狄利克雷卷积单位元ε=[n==1] 当n=1时ε=1其他等于0刘维尔函数λ(n)关于能整除n的质因子的数目

定理 μ*1

五、莫比乌斯反演

莫比乌斯反演的公式就在上面,通过好确定的g(n)简化对f(n) 的 求解就是莫比乌斯反演的精髓,而狄利克雷卷积就是到处这个公式(即证明的主要方法)

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 数学--数论--HDU 12151七夕节 Plus (因子和线性筛)

    风骨散人Chiam
  • 数学--数论--因子和线性筛 (模板)

    风骨散人Chiam
  • 数学--图论--莫比乌斯线性筛模板

    风骨散人Chiam
  • python学习笔记 函数

    在python中,函数是一等对象。编程语言理论家把“一等对象”定义为满足以下条件的程序实体:

    py3study
  • 深度学习Pytorch检测实战 - Notes - 第1&2章 基础知识

    物体检测技术,通常是指在一张图像中检测出物体出现的位置及对应的类别。我们要求检测器输出5个量:物体类别、

    肉松
  • 如何学python 第八课 流程控制-For,While,循环语句,函数

    循环语句 也许你会问,什么是‘循环’?在脚本程序里,循环就是‘在一定情况下一次又一次的执行某些代码’。举个例子来说,假设你很饿,桌上有好多好多个馒头,当你依旧饿...

    用户1631416
  • 教你构建机器学习项目:吴恩达新书《Machine Learning Yearning》

    【导读】本文主要介绍吴恩达最近正在编写的新书《Machine Learning Yearning》,旨在教你如何构建机器学习项目,它与吴恩达之前机器学习课程有所...

    WZEARW
  • 图插值激活提高数据高效深度学习的自然精度和鲁棒精度

    原文标题:Graph Interpolating Activation Improves Both Natural and Robust Accuracies ...

    Jarvis Cocker
  • 无缝混合云的可行性及未来

    业界目前似乎已经被公有云和私有云所支配,但这些提供连接性的底层基础设施对于用户来说都是不可见的。事实上,云计算的主要功能之一是云的资源池可以驻留在任何地方,且弹...

    SDNLAB
  • 浅谈机器学习、量化投资 与 TensorFlow

    随着再度升级的AlphaGo战胜了柯洁大魔王,最近很多金融媒体又在热烈的讨论将人工智能运用到量化投资领域,小密圈和QQ群里也有很多朋友对此很好奇。 其实在80年...

    数说君

扫码关注云+社区

领取腾讯云代金券