首页 > 其他分享 >莫比乌斯函数平方前缀和

莫比乌斯函数平方前缀和

时间:2023-12-19 10:58:06浏览次数:31  
标签:frac 前缀 乌斯 sum sqrt mu 右式 莫比

考虑求\(\sum_{i=1}^n\mu(i)^2\)

结论是\(\mu(i)^2=\sum_{j^2|i}\mu(j)\)

考虑证明这个式子。

先证明若\(\mu(i)\neq 0\)此时\(\mu(i)^2=1\)

显然只有\(j=1\)在右式造成贡献\(1\)等式成立。

若存在\(j\neq 1\)也在右式造成贡献,那么显然\(i\)有次数\(\ge 2\)质因子了\(\mu(i)=0\)与前面假设不符。

再考虑证明\(\mu(i)=0\)

设能对右式造成贡献的是质因子分别为\(k_1,k_2,...,k_m\)

那么显然\(j\)的取值有\(2^m\)种。

我们对\(j\)取不同的质因子个数分类那么右式的贡献为\(\sum_{v=0}^{m}(-1)^{v}C(m,v)\)

利用二项式定理合并\((1+(-1))^m=0\)

证毕。

则\(\sum_{i=1}^n\mu(i)^2=\sum_{j=1}^{\sqrt n}\mu(j)\cdot \lfloor\frac{n}{j^2}\rfloor\)

可以\(\sqrt n\)时间内求出。

进一步的考虑到\(\frac{n}{j^2}\)只有\(n^{\frac{1}{3}}\)种取值

只需预处理\(\mu(j)\)前缀和即可以在\(n^{\frac{1}{3}}\)求出,但是此时求前缀和已经是\(\sqrt n\)了就没必要再优化了。

标签:frac,前缀,乌斯,sum,sqrt,mu,右式,莫比
From: https://www.cnblogs.com/chdy/p/17913174.html

相关文章

  • 枚举子集&高维前缀和学习笔记
    枚举子集首先\(n\)位二进制数可以表示一个大小为\(n\)的集合的所有子集。接下来的问题均用二进制数展开。一种暴力的想法是枚举所有数然后判一下是否满足条件,单次时间复杂度\(O(2^n)\),对所有数做一遍就是\(O(4^n)\)。发现有很多枚举是无用的,考虑怎么样让每次枚举出来的都......
  • 前缀和,差分,二叉堆
    目录前缀和一维数组前缀和二维数组前缀和差分二叉堆前缀和一维数组前缀和代码如下:for(inti=0;i<n;i++){if(i==0)y[i]=x[i];elsey[i]=y[i-1]+x[i];}或者for(inti=1;i<=n;i++){y[i]=y[i-1]+x[i];}二维数组前缀和代码如下:for(inti=1;i<=n;i++){f......
  • 【算法】【线性表】最长公共前缀
    1 题目给k个字符串,求出他们的最长公共前缀(LCP)样例1:输入:k个字符串=["ABCD","ABEF","ACEF"]输出:"A"解释:公共最长前缀是"A".样例2:输入:k个字符串=["ABCDEFG","ABCEFG","ABCEFA"]输出:"ABC&q......
  • 莫比乌斯反演
    定义\[\mu(n)=\begin{cases}1~~~~~~~~~~~~~~\text{(n=1)}\\0~~~~~~~~~~~~~~\text{(n存在完全平方因子)}\\(-1)^{\omega(n)}~~\text{(otherwise)}\end{cases}\]式子\[\sum_{d|n}\mu(d)=[n=1]\]证明:设\(n\)的本质不同质因子为\(p_1,p_2,...,p_k\),则选同一......
  • 高维前缀和
    对于求高维前缀和,我的理解是在维度数乘总点数的复杂度下求前缀和。首先可以先看看二维前缀和。如果使用容斥的方法,像这样:for(inti=1;i<=n;i++){ for(intj=1;j<=m;j++){ f[i][j]=a[i][j]+f[i-1][j]+f[i][j-1]-f[i-1][j-1]; }}那么就是\(2^w\timesn\timesm\)。(\(w\)是......
  • 刷题 字典树 LCP(最长公共前缀)
    2023.12.5cf1902E字典树的功能根据字典树的概念,我们可以发现:字典树的本质是把很多字符串拆成单个字符的形式,以树的方式存储起来。所以我们说字典树维护的是”字典“。那么根据这个最基本的性质,我们可以由此延伸出字典树的很多妙用。简单总结起来大体如下:1、维护字符串集合(即......
  • 2023年广东工业大学腾讯杯新生程序设计竞赛不知道叫什么名字(前缀和)
    需要的是男生女生数量相同,做个转化,女生变成-1,然后求一遍前缀和,我们希望找到最长的满足\(sum(l,r)=0\)的区间也就是\(sum(r)-s(l-1)=0\)考虑枚举右端点,找到最左端和它相等的sum就是对于当前右端点的最长的。最开始想了个二分答案的假做法,011100,这里答案是6,长度为4不满足......
  • 前缀和/差分——acwing算法基础课笔记
    个人笔记,欢迎补充,指正。一维前缀和对于数组:a[1],a[2],a[3]...a[n];其前缀和数组为s[i]=a[1]+a[2]+...+a[i];下标必须从1开始求前缀和1for(inti=1;i<n;++i)2s[i]=s[i-1]+a[i];s[0]需要定义为0作用求原数组里一段数(l,r)的和......
  • CCF认证——202109-2 贡献的变化——差分维护,前缀和算答案
    https://www.acwing.com/problem/content/4010/http://118.190.20.162/view.page?gpid=T130脑子一热抱着玩的心态试了一下三分,当然炸了,就当初认识三分了。正解是考虑p的变化的影响,p变成p+1的时候,答案的值取决于p属于相邻递增数对的值域区间的数量。也可以考虑递减的情况,两......
  • 莫比乌斯反演
    今日又一次学习了莫比乌斯反演,终于理解了。问题:求有多少数对\((x,y)\),\(1\lex\len\),\(1\ley\lem\),\(\gcd(x,y)=1\)。莫比乌斯函数:\(\mu(d)=\left\{\begin{matrix}1&d=1\\(-1)^k&d=\prod_{i=1}^{k}p_i(p_i\nep_j)\\0&else\end{matrix}\right.......