Number Theory

莫比乌斯反演可以用于优化一类式子的计算。 莫比乌斯函数 定义 莫比乌斯函数的定义如下： $$ \mu(n)= \begin{cases} 0 & \exists\ p^2 \mid n \wedge p>1\\\\ (-1)^k & n=\prod_{i=1}^{k} p_i \end{cases} $$ 也就是说，如果 $n$ 含有平方约数，则 $\mu(n)=0$，否则 $\mu(n)=(-1)^k$，其中 $k$ 为 $n$ 中的本质不同的质约数个数。 性质 积性函数 $\mu(n)$ 为积性函数，证明如下： 设 $a,b$ 满足 $\gcd(a,b)=1$。 若 $a,b$ 其中一个数含有平方约数，则它们的乘积也一定含有平方约数，此时它们的莫比乌斯函数值都为 $0$，即 $\mu(ab)=\mu(a)\mu(b)=0$。 否则 $a,b$ 都不含有平方约数，则设它们的质约数个数分别为 $k_a,k_b$，则 $\mu(a)=(-1)^{k_a},\mu(b)=(-1)^{k_b}$，因为满足 $\gcd(a,b)=1$，故 $ab$ 的质约数个数为 $k_a+k_b$，$\mu(ab)=(-1)^{k_a+k_b}=(-1)^{k_a}(-1)^{k_b}=\mu(a)\mu(b)$。 Q.E.D. 与常数函数的卷积 这个性质十分重要，是反演的基础。这个性质可以写成 $I * \mu= \epsilon$，或者： $$ \sum_{d\mid n}I(\frac{n}{d})\mu(d)=\epsilon(n) $$ 经常简记为： $$ \sum_{d\mid n} \mu(d) = [n=1] $$ $\epsilon$ 是 Dirchlet 卷积的单位元函数。...

解各种同余方程是同余问题的一个重要部分，本文介绍各种同余方程的求解方法。 二元线性不定方程 形式 不定方程的范围很广泛，只要没有确定的解的方程都可以叫不定方程。本文主要讨论数论中的不定方程。 $$ ax+by=c\ (a,b,c,x,y\in \mathrm{Z}) $$ 形如上面这种形式，满足各项的系数和解均为整数的方程就是数论中的不定方程。 求解 Theorem 1：$\forall a, b \in \mathrm{Z}$，一定存在 $x,y\in \mathrm{Z}$，使得 $ax+by=\gcd(a,b)$。 这个定理又叫做裴蜀定理，根据这个定理，可以得出不定方程 $ax+by=c$ 有解的充要条件就是 $\gcd(a,b)\mid c$。记 $d=\gcd(a,b)$，则我们可以先求出 $ax'+by'=d$ 的解，再令 $x=\frac{c}{d}x',y=\frac{c}{d}y'$，就得出原方程的一组解。 求 $x',y'$ 的过程可以用扩展欧几里得算法，即 exgcd 解决。 Theorem 2：若 $\gcd(a,b)=1$，且 $x_0,y_0$ 是方程 $ax+by=c$ 的一组解，则该方程的通解为 $x=x_0+kb,y=y_0-ka$，其中 $k\in \mathrm{Z}$。 换句话说，$x,y$ 这两个解是具有周期性的。根据这个定理，我们知道一定有一个 $x\in [0,b)$，而对于方程 $ax+by=c$，则一定有一个 $x\in [0,\frac{b}{\gcd(a,b)})$，由此可以求一个不定方程的一个元的最小非负整数解，具体地，假设知道了一个解 $x_0$，则最小非负整数 $x=(x_0 \bmod m + m) \bmod m$，其中 $m=\frac{b}{\gcd(a,b)}$。 总结一下，求解二元线性不定方程 $ax+by=c$ 的流程如下： 求出 $ax+by=\gcd(a,b)$ 的一组解 $x',y'$，并根据 $\gcd(a,b)\mid c$ 判断方程有无解 令 $x=\frac{c}{\gcd(a,b)}x',y=\frac{c}{\gcd(a,b)}y'$，$x,y$ 为 $ax+by=c$ 的一组解 若需要求 $x$ 的最小非负整数解，则将 $x=(x_0 \bmod m + m) \bmod m$ 作为最终的答案，其中 $m=\frac{b}{\gcd(a,b)}$ 线性同余方程 形式 $$ ax \equiv c \pmod{p} $$ 形如这样的方程，就被称线性同余方程。...

欧拉函数 $\varphi(n)$ 是一个重要的数论函数，它表示 $[1, n]$ 中与 $n$ 互质的数的个数。 欧拉函数性质 积性函数 积性函数的定义是：如果一个函数 $f(n)$ 满足 $\gcd(a,b)=1$ 时 $f(ab)=f(a)f(b)$，则 $f(n)$ 为积性函数。 若无需 $\gcd(a,b)=1$ 就有 $f(ab)=f(a)f(b)$，则它为完全积性函数。 $$ n = \prod p_i^{c_i}\\\\ f(n) = \prod f(p_i^{c_i}) $$ 一般来说，各种积性函数都是可以使用欧拉筛计算出来的，尽管方法各不相同。 $\varphi(n)$ 也是积性函数，证明就省略了。 计算公式 因为 $\varphi(n)$ 是积性函数，所以我们可以先研究 $\varphi(p^k)$ 怎么计算。$p^k$ 的约数有 $1, p, p^2, \dots, p^k$，而 $p^2, \dots, p^k$ 都含有 $p$ 这个约数，如果一个数不与 $p^k$ 互质，则一点有 $p$ 这个约数，我们只有知道小于等于 $p^k$ 的数中 $p$ 的倍数有多少即可。由此得出 $\varphi(n) = p^k - \frac{p^k}{p} = p^k - p^{k-1}=p^k\frac{p-1}{p}$。...