当前位置 博文首页 > Wtothey_的博客:狄利克雷卷积+莫比乌斯反演+杜教筛
狄利克雷卷积与数论函数构成群,四个性质:
- 封闭性
- 结合律
- 逆元
- 幺元
特殊卷积
,互为逆元
欧拉函数+莫比乌斯函数点这里
定义:
反演:
证明:(狄利克雷卷积)
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
定义:
反演:
证明:
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
性质:
- 最多块,O()
- 每一块最后一个i值为
ll aliquot_patition(int n){
ll ans = 0;
for(int l = 1, r = 0; l <= n; l = r + 1) {
r = n / (n / l); // 求区间的右端,这是一个数学规律
ans += 1ll * (r - l + 1) * (n / l); //个数*数值
}
return ans;
}
低于线性时间复杂度上求解积性函数的前缀和(n很大的时候)
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
基本套路:
? ? ? ? ? ? ? ? ? ? ? ?构造积性函数h和g,h = f * g,
? ? ? ? ? ? ? ? ? ? ? ?记? ? ???,? 接下来求? ? ? ? ?
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??
? ? ? ? ? ? ?先枚举d,则i' = i*d(乘)? ? ? ? ? ?
? ? ? ? ? ? ?代换S? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ???
? ? ? ? ? ? ?提出g(1)? ? ? ? ? ? ? ??? ? ? ? ? ? ??
对后面的式子乘除分块后,时间复杂度O(n^2/3)
应用
一、
? ? ? ? ? ? 设,即,g(1) = 1
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
二、
? ? ? ? ? ?设,即 h(i) = Id(i),g(1) = 1
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ? ? ? ? ? ? ?
三、
? ? ? ? ? ? ? ? ? ? ?先考虑狄利克雷卷积形式:
? ? ? ? ? ? ? ? ? ? 配g(n) = Id(n)?? ? ? ? ? ??? ? ? ? ???
? ? ? ? ? ? ? ? ? ? 则? ? ? ? ? ? ? ? ? ? ? ??? ? ? ? ? ? ??
? ? ? ? ? ? ? ? ? ? 由此第一项可以由平方和公式?O(1)算出,后面分块。
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
杜教筛取自:https://www.cnblogs.com/peng-ym/p/9446555.html
?
cs