莫比乌斯函数

定义

根据唯一分解定理，\(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\)。

定义

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

定义

欧几里得算法用于求两个正整数的最大公因数，其内容为：设\(\gcd(a,b)\)为正整数\(a,b\)的最大公因数，则\(\gcd(a,b)=\gcd(b,a \bmod b)\)。