分类: 第二章 数论函数

6 篇文章

第一节 基础知识
重要引理 abc=abc 数论分块 洛谷P1403 题目大意: 设f(x)x的约数个数,求i=1nf(i) 分析: 枚举约…
第二节 莫比乌斯函数+容斥定理
较简单的容斥 XMU区域赛选拔D 塔子哥数数 题目大意: 设 g(x) 为莫比乌斯函数的绝对值,把 g(1)g(2)g(3)...g(n) 连起来看成一个10进制数,其中 g(1) 是最高位,那么这个数是多少。 解题思路: 正难则反,我们可以先考虑所有位是 1 ,再刨除 g(i)=0 的位置。 计算所有位是 1n位数…
第三节 莫比乌斯反演
形式与套路式 划重点!一切莫比乌斯反演题推柿子都等价于以下套路! $$ \begin{aligned} \left[gcd(i,j)=1\right]&\iff\sum_{d\mid gcd(i,j)}\mu(d)\cr \sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)]&\iff\sum_{d}\sum_…
第四节 杜教筛
核心柿子 我们要求积性函数 f 的前缀和。设: S(n)=i=1nf(i) 我们找到另一个积性函数 g,则有: $$ g(1)S(n)=\sum_{i=1}^{n}(f * g)(i)-\sum_{i=2}^{n}g(i)\cdot S\left(\left\lfloor\frac{n}{i}\right\rfl…
第五节 min25 筛
min25 筛分为两部分。第一部分可以求质数点值的前缀和(例如:n 以内的质数之和),第二部分可以处理积性函数 f(x) 前缀和,要求 f(p) 是一个低阶多项式(如:f(p)=p2+p),且 f(pc) 可快速求值。 以下介绍均以洛谷模版题为例:洛谷P5325 :f(pk)=pk(pk1) 第一部分-求质数点的…