前置知识

一、整除分块

即按照 \(\lfloor \frac{n}{i} \rfloor\) 的值域进行分块，块数 $ \leq \lfloor 2\sqrt n \rfloor $。分 $i \leq \lfloor \sqrt n \rfloor $ ，$ i > \lfloor \sqrt n \rfloor $ 讨论。

\(i\) 所在块的右端点为 $ \lfloor \frac{n}{ \lfloor \frac{n}{i} \rfloor } \rfloor $ ，代码即
$ r=n/(n/l) $

这样，我们可以把 \(O(n)\) 的求 $ \sum _{i=1}^{n} \lfloor \frac{n}{i} \rfloor * f(i)$ 值过程变为 \(O(\sqrt n)\) ( \(f(i)\)用前缀和处理 )

• 无关的小知识

\(1^2+2^2+3^2+...+n^2=\frac{n(n+1)(2n+1)}{6}\)

\(1^3+2^3+3^3+...+n^3=\frac{n^2(n+1)^2}{4}\)

另外，在做题的时候时刻关注的是式子的形式和范围，除数不为0，r不大于n

二、普通生成函数

形如 \(f(x)=\sum _n a_nx^n\)，此处a可以有限也可以无限

如序列 \(a=1,3,5,7...\) (编号从0开始) 的生成函数是 $ \sum _{n \geq 0} (2n+1)x^n$ ，如果a有通项公式，则它的普通生成函数的系数就是通项公式

基本运算

考虑 \(a,b\) 的普通生成函数 \(f(x),g(x)\)

加法，$ f(x) \pm g(x) =\sum _n (a_n \pm b_n)x^n$ ，即 $ f(x) \pm g(x) $ 是序列 $ q_n = (a_n \pm b_n) $ 的普通生成函数

乘法，或卷积，$ f(x)g(x)= \sum_n x^n \sum_{i=0}^n a_i b_{n-i} $，即 \(f(x)g(x)\) 是序列 \(q_n=\sum_{i=0}^n a_i b_{n-i}\) 的普通生成函数

关键在构造，一般指数是题中给的限制，某项系数是最终答案

可以解决多重集组合数

三、指数生成函数

形如 $f(x)=\sum_{n \geq 0} a_n \frac{x^n}{n!} $

这里，如果原数列是有限的，就把大于数列上界的 \(a_n\) 设为 0 即可

little question: 封闭形式如何得到？(坑)

加法同上

乘法（卷积），

\(f(x)g(x)=\sum_{i \geq 0} a_i \frac{x^i}{i!} \sum_{j \geq 0} b_j \frac{x^j}{j!}\)

\(=\sum_{n \geq 0} x^n \sum_{i=0}^n a_i b_{n-i} \frac{1}{i!(n-i)!}\)

$=\sum_{n \geq 0} \frac{x^n}{n!} \sum_{i=0}^{n} \frac{n!}{i!(n-i)!} a_i b_{n-i} $

\(=\sum_{n \geq 0} \frac{x^n}{n!} \sum_{i=0}^{n} C_n^i a_i b_{n-i}\)

即 \(f(x)g(x)\) 是序列 \(q_n=\sum_{i=0}^{n} C_n^i a_i b_{n-i}\)

可以解决多重集排列数

四、狄利克雷生成函数

形如 \(f(x)=\sum_{n>0} \frac{a_n}{n^x}\)

乘法（卷积），

\(\sum_{i>0} \frac{a_i}{i^x} \sum_{j>0} \frac{b_j}{j^x}\)

\(=(\frac{a_1}{1^x}+\frac{a_2}{2^x}+\frac{a_3}{3^x}+\frac{a_4}{4^x}+...)(\frac{b_1}{1^x}+\frac{b_2}{2^x}+\frac{b_3}{3^x}+\frac{b_4}{4^x}+...)\)

\(=\frac{a_1b_1}{1^x}+\frac{a_1b_2+a_2b_1}{2^x}+\frac{a_1b_3+a_3b_1}{3^x}+\frac{a_1b_4+a_2b_2+a_4b_1}{4^x}+...\)

\(=\sum_{n>0} \frac{1}{n^x} \sum_{d|n} a_db_{\frac{n}{d}}\)

五、积性函数

\(f(1)=1\)，当\(gcd(a,b)=1\)时，有\(f(ab)=f(a)f(b)\)，则\(f(n)\)为积性函数

欧拉函数和莫比乌斯函数都是积性函数

欧拉函数

\(\varphi(n)=\sum_{i=1}^n [gcd(i,n)=1]\)

又 \(\varphi(n)=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_s})\)，其中p为n的质因数

即n以内，和n互质的数的个数

性质：\(\sum_{d|n} \varphi(d)=n\)

证明：将以n为分母，且比1小的非负分数写出来，化简后按分母归类，发现每一类 \(d\) 的个数都是 \(\varphi(d)\)

正主出场：莫比乌斯函数

定义：

\(\mu(n)=\left\{ \begin{array}{rcl} 1 & & n=1 \\ (-1)^s & & n=p_1p_2...p_s \\ 0 & & \text{n包含相同质因子}\\ \end{array} \right.\)

性质： $\sum_{d|n} \mu(d)=[n=1] $

简单证明:

\(n>1\) 时，\(n=p_1^{a_1}p_2^{a_2}..p_s^{a_s}\)

令 \(n'=p_1p_2...p_s\)

又 \(\sum_{d|n} \mu(d)=\sum_{d|n'}\mu(d)\)

约数由质因子的成绩构成，又有容斥原理

\(\sum_{d|n'}\mu(d)=C_s^0+(-1)C_s^1+(-1)^2C_s^2+...+(-1)^sC_s^s\)

\(=(1+(-1))^s\)

\(=0\)

与欧拉函数的联系：\(\sum_{d|n} \mu(d) \frac{n}{d} = \varphi(n)\)

证明是把n提出来，因式分解，化成欧拉函数的形式。

性质应用：\([gcd(i,j)=1]=\sum_{d|gcd(i,j)} \mu(d)\)