莫比乌兹反演

2024-03-20 20:59
文章标签 反演 莫比 乌兹

本文主要是介绍莫比乌兹反演,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

莫比乌兹反演算是数论中一个神奇的东东,理解起来有点吃力,对它的证明更是望而却步,好了记住结论打出模板比赛的时候用用就好~~~

首先说一下莫比乌兹反演的公式和性质:是定义在非负整数集合上的两个函数,并且满足条件,那么我们得到结论

 

     

 

在上面的公式中有一个函数,它的定义如下:

 

    (1)若,那么

    (2)若均为互异素数,那么

    (3)其它情况下

 

 

对于函数,它有如下的常见性质:

 

    (1)对任意正整数

  

                            

 

        (2)对任意正整数

 

         

下面是找到的简单的证明,不过完全看不懂啊

有了上面的知识,现在我们来证明莫比乌斯反演定理。

 

证明

 

 

证明完毕!

 

6666666

还有另一种常用描述:

 

     





莫比乌兹反演主要是用来代替一些复杂的容斥原理的方便简单的方法,可以说灵活运用莫比乌兹反演对于提高编码的准确性和代码的效率有很重要的意义。

这篇关于莫比乌兹反演的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/830706

相关文章

hdu6053 TrickGCD 莫比乌斯反演

TrickGCD Time Limit: 5000/2500 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others) Problem Description You are given an array  A  , and Zhu wants to know there are how many d

学习笔记 ---- 莫比乌斯反演总结

文章目录 概述前置知识数论分块狄利克雷卷积积性函数 莫比乌斯函数定义性质 莫比乌斯反演因子形式倍数形式 例题周期性字符串互质数对[NOI2010D1T1]能量采集BZOJ2820 YY的GCD[SDOI2015] 约数个数和BZOJ4407 于神之怒加强版【BZOJ2693】jzptab最小公倍数之和[bzoj3529-Sdoi2014] 数表 练习题51nod 1675 序列变换BZOJ3

BZOJ 2440 2301 莫比乌斯应用

http://www.lydsy.com/JudgeOnline/problem.php?id=2440 Description 小 X 自幼就很喜欢数。但奇怪的是,他十分讨厌完全平方数。他觉得这些 数看起来很令人难受。由此,他也讨厌所有是完全平方数的正整数倍的数。然而 这丝毫不影响他对其他数的热爱。  这天是小X的生日,小 W 想送一个数给他作为生日礼物。当然他不能送一 个小X讨厌

莫比乌斯反演 两种形式

莫比乌斯反演在数论中占有重要的地位,许多情况下能大大简化运算。那么我们先来认识莫比乌斯反演公式。   定理:和是定义在非负整数集合上的两个函数,并且满足条件,那么我们得到结论           在上面的公式中有一个函数,它的定义如下:       (1)若,那么     (2)若,均为互异素数,那么     (3)其它情况下     对于函数

CodeForces 547C. Mike and Foam 莫比乌斯反演

题意:给定一个长度为n的数列a,和q个操作(1<= n,q <= 2*10^5, 1 <= a[i] <= 5*10^5 ) 需要维护一个多重集合Q. 每个操作给出一个下标i,如果a[i]属于Q那么把a[i]从Q中拿走,如果a[i]不属于Q,那么把a[i]加入Q中。 每次操作后询问Q中,有多少对i,j满足条件 i<j 且 gcd(a[i],a[j])=1 这个性质的维护比较困难,直

Python星载气溶胶数据处理与反演分析

在当前全球气候变化和环境污染问题日益突出的背景下,气溶胶研究显得尤为重要。气溶胶在大气中由直径范围在0.01微米至10微米固体和液体颗粒构成,直接或间接影响地球辐射平衡、气候变化和空气质量。尤其在“碳中和”目标的驱动下,研究气溶胶对“碳中和”的气候影响及其环境效应,不仅对科学研究具有重大意义,同时也为政策制定提供了重要依据。 MODIS(中分辨率成像光谱仪)和CALIOP(云-气溶胶偏振激光雷达

基于Python星载气溶胶数据处理与反演分析

原文链接:基于Python星载气溶胶数据处理与反演分析https://mp.weixin.qq.com/s?__biz=MzUzNTczMDMxMg==&mid=2247606689&idx=1&sn=bcdca97812e5e21e1bf539eafa49a48b&chksm=fa826046cdf5e95059f4ebc5ae6120b8e909883dd1d7c0eb4a5897e79df1

HDU 1695 GCD 容斥原理/莫比乌斯反演

题意: 给你两个区间[a,b],[c,d],还有一个k。让你从区间[a,b]中找出x,[c,d]中找出y,问共有多少组(x,y)使得gcd(x,y)=k。 (x,y)和(y,x)算一组。 思路: 参考:http://blog.csdn.net/yang_7_46/article/details/9072533 容斥。 普通容斥: *如果gcd(x,y)=k,则gcd(x/k

SPOJ 7001 Visible Lattice Points(莫比乌斯反演)

莫比乌斯反演,注意0的情况特殊考虑下就可以了 #include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int N = 1000005;int mo[N], prime[N], pn;bool vis[N];void Moblus() {memset(vis, false, siz

精密单点定位(PPP)数据处理反演潮汐(四)

前段时间,我又尝试用TerraPos处理一下SeaPath330的原始姿态和定位数据,看看反演潮位的效果如何。 首先,怎么预处理SeaPath330的定位和姿态数据, 记录格式如下1901200054.l09和1901200054.l10,咨询了SeaPath330的技术张工,对话如下: 张工,有个问题咨询一下,Seapath记录的RTCM数据格式.l09和IMU原始数据.l10怎么转成ri