Tags/Mathematics

莫比乌斯反演可以用于优化一类式子的计算。 莫比乌斯函数 定义 莫比乌斯函数的定义如下： μ(n)={0∃ p2∣n∧p>1(−1)kn=∏i=1kpi \mu(n)= \begin{cases} 0 & \exists\ …

解各种同余方程是同余问题的一个重要部分，本文介绍各种同余方程的求解方法。 二元线性不定方程 形式 不定方程的范围很广泛，只要没有确定的解的方程都可以叫不定方程。本文主要讨论数论中的不定方程。 ax+by=c (a,b,c,x,y∈Z) …

Burnside 引理和 Pólya 定理主要用于解决计算本质不同方案数的计数问题。 群论 基本定义 群可以看成是一个由集合和某个二元运算组成的二元组 (S,⋅)(S,\cdot)(S,⋅)，这里的 ⋅\cdot⋅ 就代表一个二元运算，这个 …

欧拉函数 φ(n)\varphi(n)φ(n) 是一个重要的数论函数，它表示 [1,n][1, n][1,n] 中与 nnn 互质的数的个数。 欧拉函数性质 积性函数 积性函数的定义是：如果一个函数 f(n)f(n)f(n) 满足 …

拉格朗日插值是众多插值算法中的一种，插值是通过一些点来求出过这些点的多项式函数的过程。 算法思想 构造函数 给出 n+1n + 1n+1 个点 …

高斯消元主要用于求解线性方程组的解，同时可以解决某些有后效性的 DP 问题， 算法思想 增广矩阵 为了更方便地求解方程组，可以将系数和常数项放入矩阵，接下来就可以用一些矩阵的操作来消元了。 比如有一个方程组如下： …