莫比乌斯函数及莫比乌斯反演

莫比乌斯函数

定义

根据唯一分解定理,\(n=\prod_{i=1}^{k} p_i^{a_i}\)\(\mu\)定义为 \[\mu(n)=\begin{cases}\mu(1)=1\\ \mu(n)=(-1)^k,\quad \forall a_i=1\\ \mu(n)=0,\quad \exists a_i>1\end{cases} \]

阅读更多

类欧几里得算法

定义

给定\(a,b,c,n\)求对应函数的值:

\(f(a,b,c,n)=\sum_{i=0}^n\lfloor\frac{ai+b}{c}\rfloor\)

\(g(a,b,c,n)=\sum_{i=0}^n i\lfloor\frac{ai+b}{c}\rfloor\)

\(h(a,b,c,n)=\sum_{i=0}^n\lfloor\frac{ai+b}{c}\rfloor^2\)

阅读更多

欧拉函数

定义

对于正整数\(n\),欧拉函数是小于等于\(n\)的数中与\(n\)互质的数的数目,写作\(\varphi (n)\)。特别的,\(\varphi (1)=1\)

阅读更多

Treap

定义

“维护一个有序数列,有插入、删除、查询第k大、查询前驱、后继等操作”,对于这种问题,我们常用到二叉排序树(BST,Binary Sort Tree,也称二叉查找树、二叉搜索树)这种数据结构,而Treap就是对它的一种优化

阅读更多

树状数组

定义

树状数组(Binary Indexed Tree,BIT)是用于解决区间查询,单点修改的一种数据结构。

阅读更多

哈夫曼树

定义

给定\(n\)个权值作为\(n\)个叶子结点,构造一棵二叉树,若带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。

阅读更多

扩展欧几里得算法

定义

扩展欧几里得算法用于已知\(a,b\),求解一组\(x,y\),使得他们满足\(ax+by=\gcd(a,b)=d\)

阅读更多
Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×