数论相关

发表于 2024-10-05 更新于 2025-04-15 分类于具体数学 Waline：

整除性及相关
素数及相关
阶乘
- Example(《具体数学》4.55)
互素
同余
积性函数
整值函数

本文除特殊说明,所涉及数均为整数.

整除性及相关

如果$m>0$且$\cfrac{n}{m}$是一个整数,我们就说$m$整除$n$,记作$m|n$.

能同时整除两个数$n$和$m$的数称为$n$和$m$的公因子,所有公因子中最大的那个称为最大公因子,记作$\gcd(n,m)$.而最小的能同时被$n$和$m$整除的非零数被称为他们的最小公倍数,记作$lcm(n,m)$.不难发现$lcm(n,m)\gcd(n,m)=nm$.

欧几里得算法

欧几里得算法基于以下定理:

$\gcd(0,n)=n$且$\gcd(n,m)=\gcd(n\mod m,m),m>0$.

考虑证明,首先,$\forall k\in\mathbb{Z}$,$n$和$m$的公因子一定是$n$和$m+kn$的公因子,这是显然的.因此,$n$和$m$的公因子一定是$m$和$n-m\lfloor\cfrac{n}{m}\rfloor$的公因子,而反之亦然.

另外有如下性质:

$\gcd(kn,km)=k\gcd(n,m)$以及$lcm(kn,km)=k\ lcm(n,m)$.
若$a\bot b$,则$\gcd(a^m-b^m,a^n-b^n)=a^{\gcd(n,m)}-b^{\gcd(n,m)}$.
如果$n^a\equiv 1\pmod m\and n^b\equiv 1\pmod m$,则$n^{\gcd(a,b)}\equiv 1\pmod m$.

(1)的证明较为显然,我们考虑(2)的证明.

不妨假设$n\leq m$,当$n=m$时显然成立.

当$n<m$时:

假设$a>b$,考虑$\gcd(a^m-b^m,a^n-b^n)=\gcd(a^m-b^m-k(a^n-b^n),a^n-b^n)$.

取$k=b^{m-n}$,则: \[ \gcd(a^m-b^m,a^n-b^n)=\gcd(a^m-b^{m-n}a^n,a^n-b^n)\\ =\gcd(a^n(a^{m-n}-b^{m-n}),a^n-b^n) \] 由于$a\bot b$,所以显然$a^n-b^n\bot a^n$,于是: \[ \gcd(a^m-b^m,a^n-b^n)=\gcd(a^{m-n}-b^{m-n},a^n-b^n) \] 自然得证.

接下来考虑(3)的证明:

如果$a=b$,显然得证.不然,不妨设$a>b$注意到: \[ n^a\equiv 1\pmod m\\ n^a-n^{a-b}n^b\equiv 1-n^{a-b}\pmod m\\ n^{a-b}\equiv 1\pmod m \] 自然得证.

一些性质

令$n,m\in\mathbb{N_+}$.

$k|n\and k|m\Leftrightarrow k|\gcd(n,m)$.
$\sum_{m|n}a_m=\sum_{m|n}a_{\frac{n}{m}}$.
$\sum_{m|n}\sum_{k|m}a_{k,m}=\sum_{k|n}\sum_{l|(\frac{n}{k})}a_{k,kl}$.

另外,$\gcd$有一个很著名的性质:对于数字$n,m$,找到最小的正整数$x$满足$\exists y\in \mathbb N$,$xn=ym$.

首先令$g=\gcd(n,m)$,我们自然有$x\frac{n}{g}=y\frac{m}{g}$,也就相当于$x\frac{n}{g}\equiv 0\pmod{\frac{m}{g}}$,由于$\gcd(\frac{n}{g},\frac{m}{g})=1$,所以左边的$\frac{n}{g}$可以用逆元消掉,显然最小正整数解为$x=\frac{m}{g}$.

Example1([CF1656H]Equal LCM Subsets)

注意到插入可能有点小困难,我们考虑从全集中删除:注意到如果对于一个数字的某一个质因子,如果它的指数大于了对方集合中相同质因子的最大指数,那这个数一定不可能存在,直接删掉.不难发现删完后就是合法的了.

首先,数据范围不允许我们判断质因子,那么怎么做呢?

显然合法的条件等价于$a_i|lcm(b),\forall 1\leq i\leq n$(当然这个还要反过来再写一遍,两个式子一起才是充要条件,这里为了方便只写一个),这个条件等价于$\gcd_{j=1}^n(\frac{a_i}{\gcd(b_j,a_i)})=1$.后者是方便做的.

然后上线段树处理一下,好像先random_shuffle一下再暴力删除也是对的.

基于值域预处理的快速 GCD

存在一种$O(n)$预处理,$O(1)$求任意两个小于等于$n$的数的$\gcd$的方法:

引理:

对于任意整数$n$,存在一种划分方式$n=abc$,$a$,$b$,$c$三个数要么是质数,要么$\leq \sqrt n$.

证明:

如果$n$存在一个大于等于$\sqrt n$的质因子,显然成立.

否则,使用数学归纳,我们考虑$n$的最小质因子为$p$,设$\frac n p=xyz$,不妨设$x\leq y\leq z$.

如果$x=1$,显然成立.

不然有$p\leq x\leq y\leq z$,而$pxyz=n$,那么$p^4\leq n$,$p\leq n^{\frac 1 4}$.

现在我们想要证明不存在$xp>\sqrt n$,$yp>\sqrt n$,$zp>\sqrt n$.

如果存在,我们有: \[ xyzp^3>n^{\frac 3 2}\\ np^2>n^{\frac 3 2}\\ p^2>\sqrt n\\ p>n^{\frac 1 4} \] 与我们前面的结论不符合.

因而该引理成立,并且给出了$O(n)$预处理所有数$abc$的方法.

接下来，设$m=\sqrt n$,考虑使用$O(n)$的时间求出每个小于等于$m$的数对的$\gcd$,如果我们要求$\gcd(x,y)$,设$x=abc$,显然$\gcd(x,y)=\gcd(a,y)\times\gcd(b,\frac{y}{\gcd(a,y)})\times\gcd(c,\frac{y}{\gcd(ab,y)})$.

如果$a$是质数，只需要判断$a$是否整除$y$.

否则$\gcd(a,y)=\gcd(y\mod a,a)$,因为$a\leq \sqrt n$,因而可以直接查表.

裴蜀定理

$\forall a,b,m\in\mathbb{Z}$,则$\exists x,y\in \mathbb{Z}$满足$ax+by=m$,当且仅当$\gcd(a,b)|m$.

证明如下:

若$a=0$或$b=0$,显然成立.

不然,设集合$A=\{xa+yb|x,y\in\mathbb{Z}\}$中的最小正元素$d_0=x_0a+y_0b$,该集合中显然一定有正元素.

考虑取该集合中另一个正整数$d_1=x_1a+y_1b>d_0$,注意到$d_1-d_0=(x_1-x_0)a+(y_1-y_0)b\in A$,所以$\gcd (d_1,d_0)\in A$,如果$d_0\nmid d_1$,那么$0<\gcd (d_1,d_0)<d_0$,与假设不符.所以这个集合里的所有数一定都是$d_0$的倍数.

事实上还有另一种证明方式:

如果我们定义一个非空集合$I\subseteq \Z$,满足其对加法和数乘($\forall a\in \Z,x\in I,ax\in I$)均封闭,那么我们可以证明其中存在一个唯一的数字$g$满足所有数都是$g$的倍数.

如果$I=\{0\}$,可以取$g=0$.

反之,显然其中有正有负(因为可以取$a=-1$),我们设$I_+=\{k\in I|k\geq 1\}$取$g=\min I_+$.$\forall a\in I$,不妨设$a=gq+r,r\in [0,g)$,那么$r=a+(-q)g\in I$,由于$r<g$,所以$r\notin I_+$,所以$r=0$,$a$是$g$的倍数,且显然$g$唯一.

扩展欧几里得算法

考虑求方程$ax+by=\gcd(a,b)$的一组解.

首先,如果$b=0$,那这组解显然就是$\begin{cases}x=1\\y=0\end{cases}$.

反之,我们令$c=a\mod b$,考虑求方程$cz+bw=\gcd(c,b)$的一组解.

接下来呢,考虑带入$c$,则我们求出来的即方程$(a-b\lfloor\cfrac a b\rfloor)z+bw=\gcd(a,b)$的一组解.不难发现这也就是方程$az+(w-\lfloor\cfrac a b\rfloor z)b=\gcd(a,b)$的一组解,所以原本的方程的解也就是$\begin{cases}x=z\\y=(w-\lfloor\cfrac a b\rfloor z)\end{cases}$.

另外,这个算法也可以使用矩阵形式:

首先有$\left[\begin{matrix} a\\ b \end{matrix}\right] =\left[\begin{matrix} a\\ b \end{matrix}\right]$,令$q=\lfloor\frac a b\rfloor$,那么我们有$\left[\begin{matrix} 0&1\\ 1&-q \end{matrix}\right] \left[\begin{matrix} a\\ b \end{matrix}\right]= \left[\begin{matrix} b\\ a\mod b \end{matrix}\right]$.

同样我们可以得到:$\left[\begin{matrix} x_1&y_1\\ x_2&y_2 \end{matrix}\right] \left[\begin{matrix} a\\ b \end{matrix}\right]= \left[\begin{matrix} \gcd(a,b)\\ 0 \end{matrix}\right]$,即$ax_1+by_1=\gcd(a,b)$,$(x_1,y_1)$就是一组特解.

Example1([XVII Open Cup named after E.V. Pankratiev. Grand Prix of Japan(openstrain contest 1489)E]Eel and Grid)

题意:$h\times w(h,w\leq 10^6)$的格子图,只能往下往右走,走到边界会循环,问从$(0,0)$开始走遍历走一个哈密顿回路的方案数.

这题最重要的地方其实在于观察到,由于每个点只会被走到一次(除了$(0,0)$,它会被走到两次,但只会由其它格子走来一次),因此如果抽象成图,每个格子只会有一个出边和一个入边.这意味着每个格子上面的和左边的格子必定只有一个指向它,进一步地,这意味着这两个格子的状态必然相同.

由此我们发现,每条副对角线(取膜意义下)的状态必然相同,而取膜意义下的副对角线有多少条呢?不难注意到是$d=\frac{hw}{\text {lcm}(h,w)}=\gcd(h,w)$条.也就是说,我们只需要确定这$d$条对角线的值,就可以确定整个矩阵的答案.假设$R$表示向右走,$D$表示向下走,$a_i$表示第$i$条副对角线的状态,最后的操作序列自然是$a_0a_1...a_{d-1}a_0a_1...$.

那么我们接下来要做的就是给这$d$条副对角线定向,并判断一个方案是否合法.注意到一个方案不合法当且仅当出现了多于$1$个环.那这又意味着什么呢?意味着存在一个点,它可以通过少于$hw$次走动走回自己.这显然是不被我们允许的.另一件不难发现的事是,第一个走回自己的点一定是$(0,0)$.再不难发现的是,走回自己的时候一定是经过了若干个周期:$a_0a_1...a_{d-1}a_0...a_{d-1}$,因为每次向下或者向右走都会走到下一条副对角线,而且最后要回到自己.这就注意到每一个循环$a_0a_1...a_{d-1}$内部具体什么情况是不在乎的,只在乎经历过这个过程之后会发生什么样的变化.

我们不妨假设序列$\{a\}$中有$k$个$R$,$d-k$个$D$,那会产生这种情况当且仅当$\exists x\in \mathbb{N_+},x< \frac{hw}{d}$,$\begin{cases}h|x(d-k)\\w|xk\end{cases}$.注意到这等价于寻找最小的$x$,判断其是否小于$\frac{hw}{d}$,于是条件等价于自然有$x=lcm(\frac{h}{\gcd(d-k,h)},\frac{w}{\gcd(w,k)})$,枚举$k$并判断即可.

素数及相关

定义

可以利用裴蜀定理证明素数的定义等价于$\forall a,b,p|ab\Rightarrow p|a\or p|b$.

考虑先用最基础的定义得到这个命题,考虑$p|ab,p\nmid a$,则$1=px+ay$有解,则$b=pxb+(ab)y$,右边都是$p$的倍数,所以$p|b$.

这个命题反推的话,考虑设$p=ab,a,b\ne 1$,则$p|ab$且$p\nmid a,p\nmid b$,不符.

Example1(《具体数学》4.22)

证明:在$n$进制下,若$(11...1)_n$的$1$的个数不是质数则其一定不是质数..

设$1$的个数为$m$,则$(11...1)_n=\sum_{i=0}^{m-1}n^i$.

如果$m\notin prime$,不妨设则$m=cd,c\ne 1\and d\ne 1$.

则 \[ \sum_{i=0}^{m-1}n^i=\sum_{i=0}^{c-1}n^{di}\sum_{j=0}^{d-1}n^{j}\\=(\sum_{i=0}^{c-1}n^{di})(\sum_{j=0}^{d-1}n^j) \] 显然不是质数.

唯一分解定理(算数基本定理)

任何正整数都只有一种方式以素数非减的次序写成素数的乘积.

证明:

考虑数学归纳法,设小于$n$的数全部满足.

则对于$n$,如果它不满足条件,一定存在两种分解方式$n=\prod_{i=1}^mp_i=\prod_{i=1}^kq_i$.

首先,如果$p_1=q_1$,根据归纳假设,显然不成立.

不失一般性,设$p_1<q_1$.则$q_1|p_1\prod_{i=2}^mp_i$,显然$q_1\nmid p_1$,所以$q_1|\prod_{i=2}^mp_i$,设$s=\prod_{i=2}^mp_i$,但这是不可能的,因为$s<n$,根据归纳假设,它只有一种分解方式,这种方式中显然不可能存在$p_1$.

那么根据上述证明,我们可以将一个数表示为以下形式:$n=\prod_p p^{n_p},n_p\geq 0$.

另外不难证明的一点是,假设$\sum n_p=k$,那么最小质因子一定不大于$\sqrt[k]{n}$.

Example1([CF986F]Oppa Funcan Style Remastered)

首先对$k$做pollard-Rho算法.注意到我们可以默认$q_i$是质因子,这显然不会影响答案.

然后,如果只有一个质因子,显然直接判断.

如果有两个质因子,是经典的二元不定方程.

如果有三个质因子,此时最小质因子的大小就不大于$\sqrt[3]{k}$,做同余最短路即可.

素数的个数

首先,欧几里得证明了素数有无穷多个:

假设素数有有限个,分别为$p_1,p_2,...p_m$,则$\prod_{i=1}^mp_i+1$无法被其中任何素数整除,则假设不成立.

在此基础上,我们可以定义欧几里得数:

$e_1=2,e_n=1+\prod_{i=1}^{n-1}e_i$.

令$\pi(n)$表示小于等于$n$的素数个数,有${\lim_{n\rightarrow+\infty}\cfrac{\pi(n)\times \ln n}{n}}=1$.

有切比雪夫定理(又称贝特朗假设):若$n>1,\exist p\in prime,p\in(n,2n)$.

又有狄利克雷定理:若$\gcd(a,b)=1,\{an+b\}$中包含了无穷个素数.

(顺便一提,当$a=4$或者$a=6$,$b=-1$的时候是好证明的,由于素数要么形如$6n-1$要么形如$6n+1$,或者要么形如$4n-1$要么形如$4n+1$,只需要类似证明素数无限那样乘一乘)

同时,我们还有以下结论:$\sum_{1\leq p\leq n\and p\in prime}\cfrac{1}{p}\approx \log\log n$.

证明如下: \[ \sum_{1\leq p\leq n\and p\in prime}\cfrac{1}{p}=\sum^n_{k=1}\cfrac{\pi(k)-\pi(k-1)}{k}=\sum^n_{k=1}\cfrac{\pi(k)}{k}-\sum^n_{k=1}\cfrac{\pi(k-1)}{k}\\ =\sum^n_{k=1}\cfrac{\pi(k)}{k}-\sum^{n-1}_{k=0}\cfrac{\pi(k)}{k+1}\\ =\sum^{n-1}_{k=1}\cfrac{\pi(k)}{k}+\cfrac{\pi(n)}{n}-\sum^{n-1}_{k=1}\cfrac{\pi(k)}{k+1}-\cfrac{\pi(0)}{1}\\ =\sum^{n-1}_{k=1}\cfrac{\pi(k)}{k(k+1)}+\cfrac{\pi(n)}{n}\\ = \sum^{n-1}_{k=1}{(\cfrac{1}{k\log k})}+O(\frac{1}{\log n})= O(\log \log n)+O(\frac1{\log n}) \]

Example1(《具体数学》4.20)

证明:存在一个常数$b$满足$\lfloor2^b\rfloor,\lfloor2^{2^b}\rfloor,\lfloor2^{2^{2^b}}\rfloor.,..$都是质数.

如此构造数列:设$p_1=2$,且$p_n$为满足$2^{p_{n-1}}<p_n<2^{p_{n-1}+1}$的最小质数.

通过构造不难发现:$p_{n-1}=\lfloor\log_2 p_n\rfloor$.

根据整值函数的性质,我们有$\lfloor\log_2 x\rfloor=\lfloor\log_2\lfloor x\rfloor\rfloor$.考虑反向数学归纳,考虑当$n\rightarrow +\infty$时构造满足题目条件,那么$p^{n-1}=\lfloor \log_2\lfloor2^{2^{2^{...^{b}}}}\rfloor\rfloor=\lfloor2^{2^{...^{b}}}\rfloor$,自然也满足条件.所以如果设$\log_2^{(n)}x$为不断对$x$迭代求$\log_2$做$n$次后的答案,只需构造$b=\lim_{n\rightarrow +\infty}\log_2^{(n)}p_n$即可.

Example2

求证: \[ \mu(\gcd(a,b))=0\Leftrightarrow \forall n>0,\mu(an+b)=0 \] 左推右是简单的.接下来考虑右推左.

考虑狄利克雷定理,数列$\{\frac{an+b}{\gcd(a,b)}\}$.不妨反证,假设$\mu(\gcd(a,b))\ne 0$,不妨设$p=\frac{an+b}{\gcd(a,b)}$,$p\gcd(a,b)=ax+b$,也就是$\mu(p\gcd(a,b))=0$,注意到$\mu(\gcd(a,b))\ne 0$,此时必有$p|\gcd(a,b)$,而$p$无限,$\gcd(a,b)$的素因子有限,这就导出了矛盾.

欧几里得数

定义欧几里得数:$e_1=2,e_n=1+\prod_{i=1}^{n-1}e_i$.不难发现$e_n=e_{n-1}(e_{n-1}-1)$.

费马数

定义费马数$f_n=2^{2^n}+1$.不难发现$f_n=(f_{n-1}-1)^2+1$.

另外,费马数还满足$f_n=\prod_{i=0}^{n-1}f_i+2$,我们考虑这个式子的证明:显然后面那一个连乘会得到若干项$2$的次幂,并且这些项两两不同,根据几何级数,我们有$\prod _{i=0}^{n-1}f_i+1$=$2^{2^{n}}$,于是显然得证.

Example1(《具体数学》4.17)

求证:如果$m\ne n$,则$f_m\bot f_n$.

不妨假设$m<n$,有:$\gcd(f_m,f_n)=\gcd(f_m,2)=1$.

Example2(《具体数学》4.18)

求证:若$2^n+1$是质数,则$n$是$2$的整数幂.

如果$n=qm$且$q$是奇数,我们有:$2^n+1=(2^m+1)(2^{n-m}-2^{n-2m}+2^{n-3m}...-2^m+1)$.

Miller-Rabin算法

如果判断$n$是否是质数,取$a<n$,设$n-1=d\times2^r$.

则要么$a^d\equiv 1(\mod n)$.

要么$\exists i$,使得$0\leq i<r$,$a^{d\times 2^i}\equiv -1(\mod n)$.

若一个都不满足,则n一定不是质数,不然可能是质数.

但是若取足够多的不同的$a$(如果选$m$个),那么$n$是质数的可能性更大.

此为Miller-Rabin算法,复杂度$O(m\times log_2n)$.不保证正确性.

其中a通常取质数,原因不详.（事实上，如果a取前八个小质数，在$2^{64}$内是不会出错的）

Pollard-Rho算法

对$n$做质因数分解,若能找到$a$使得$a|n$,则考虑对$\cfrac{n}{a}$和$a$分别进行质因数分解.

考虑随机$a$,若$n$有$m$个因数,那么显然随机到$a$使得$a|n$的概率为$\cfrac{m}{n}$,显然不太优秀.

考虑改变随机策略,我们考虑随机一个$a$使得$\gcd(a,n)\ne 1$,那么$\gcd(a,n)$就是$n$的一个因子.

这种情况下,随机的概率是$\cfrac{\varphi(n)}{n}$,仍然很不优秀.

考虑使用生日悖论优化,随机$k$个数$a$.两两匹配得到$k^2$个值,这些值全都不整除$n$的概率可以用生日悖论来计算.

当$k=10\sqrt{n}$时,错误的概率会很小,但是复杂度仍然很高,无法接受.

考虑构造$a_i=[(a_{i-1})^2+b]\mod n$.

考虑该数列的性质,当$b$确定时,$a$一定有循环节.

显然当$x|(a_i-a_j)$,则$x|[(a_i-a_j)\times(a_i+a_j)-b+b]$,$x|(a_{i+1}-a_{j+1})$.

因此,我们可以利用floyd判环法(双指针法)找出循环节.

并且在这个过程中,我们可以预处理出大量的$a_{i+len}-a_i$.

复杂度极其玄学,但是实际应用中不差.

狄利克雷前缀和

已知数列$a$,求数列$b$满足$b_n=\sum_{d|n}a_d$.

我们将一个数的质因数分解看作它的向量表示.更直接地,如果$n=\prod_{i=1}^kp_i^{q_i}$,其中$p_i$是第$i$大的质数.我们将其写作向量$(q_1,q_2,...,q_k)$的形式,并做高位前缀和.

可以用$O(n\log\log n)$的时间复杂度解决问题.

阶乘

我们定义$n!=\prod_{i=1}^ni$,特别地,$0!=1$.

考虑估计$n!$的大小,不难发现$(n!)^2=\prod_{i=1}^ni(n+1-i)$.

而函数$y=i(n+1-i),i\in[1,n]$显然在$i=1$和$i=n$时取最小值,而在$i=\cfrac{n+1}2$时取最大值.

那么我们有$\prod_{i=1}^nn\leq (n!)^2\leq \prod _{i=1}^n\cfrac{(n+1)^2}{4}$.

于是$n^{\frac{n}2}\leq n!\leq \cfrac{(n+1)^n}{2^n}$.

还有一种估计方式是考虑$\lim_{n\rightarrow \infty}\frac{n}{\sqrt[n] n!}$,由Stolz定理及其推论,我们知道若$a_n>0,\frac{a_{n+1}}{a_n}=a$,那么$\lim_{n\rightarrow \infty}\sqrt[n]{a_n}=a$.而我们令$a_n=\frac{n^n}{n!}$,$\frac{a_{n+1}}{a_n}=(1+\frac{1}{n})^n$,所以$\lim_{n\rightarrow \infty}\frac{n}{\sqrt[n]{n!}}=e$,于是我们可以估计$n!\sim (\frac{n}{e})^n$.

事实上有一种更准确的估计方法:$n!\sim \sqrt{2\pi n}(\cfrac{n}e)^n$.

考虑设$\varepsilon_p(n!)$为$n!$中质因子$p$的个数,我们分析一下这个函数:

首先显然有:$\varepsilon_p(n!)=\sum_{k\geq 1}\lfloor\cfrac{n}{p^k}\rfloor\leq\frac{n}{p-1}$.

我们考虑以$v_p(n)$表示$n$在$p$进制下各位数字之和,不妨设第$k$位数字为$w$.那么这个数字对于最后的答案的贡献为$w(p^{k-1}+p^{k-2}+...+1)=w\cfrac{p^k-1}{p-1}=\cfrac{wp^k-w}{p-1}$.求和得到$\varepsilon_p(n!)=\cfrac{n-v_p(n)}{p-1}$.

Example(《具体数学》4.55)

令$P_n=\prod _{i=1}^ni!$,求证:$P_n^4(n+1)\mid P_{2n}$.

考虑对于每个质因子,分开考虑它在前者和后者内出现的次数.

我们不妨将$p$和$p^k$分开考虑,于是显然下面的式子是上面的式子成立的充分条件: \[ \sum_{m\geq 1}\sum_{i=1}^{2n}\lfloor\cfrac{i}{p^m}\rfloor\geq4\sum_{m\geq 1} \sum_{i=1}^n\lfloor\cfrac{i}{p^m}\rfloor+[p^m\mid (n+1)] \] 我们不妨对上面这个式子使用数学归纳,也就是说它的充分条件是: \[ \lfloor\cfrac{2n-1}{p^m}\rfloor+\lfloor\cfrac{2n}{p^m}\rfloor\geq 4\lfloor\cfrac{n}{p^m}\rfloor+[n\equiv -1\pmod {p^m}]-[n\equiv 0\pmod {p^m}] \] 这个式子,当$1\leq n\leq p^m$时显然成立.而当$n$每增大$p^m$的时候,左右两边同时增大$4$,于是也是成立的,由此可以数学归纳.

互素

如果两个数$n$和$m$满足$\gcd(n,m)=1$,我们称他们互素,记作$n\bot m$.

我们显然有这样两条性质:

$\cfrac{n}{\gcd(n,m)}\bot \cfrac{m}{\gcd(n,m)}$.
$k\bot n\and k\bot m\Leftrightarrow k\bot nm$.

Example1(《具体数学》4.42)

证明:如果两个分数$\cfrac{m}{n}$和$\cfrac{m'}{n'}$满足$n\bot m$且$n'\bot m'$,则$(mn'+m'n)\bot(nn')$的充分必要条件是$n\bot n'$.

首先,如果$\gcd(n,n')\ne 1$,显然不可能满足条件,必要性得证.

考虑充分性,如果$n\bot n'$,则只需证明$n\bot (mn'+m'n)\and n'\bot (mn'+m'n)$即可.

而$\gcd(n,mn'+m'n)=\gcd(n,mn')=1$,另一个式子同理,于是得证.

Example2

证明:$\sum_{0\leq k<m}f(k)=\sum_{d|m}\sum_{0\leq k<d}f(\frac{km}{d})[k\bot d]\\$.

考虑: \[ \sum_{0\leq k<m}f(k)=\sum_{d|m}\sum_{0\leq k<m,d|k}f(k)[\gcd(k,m)=d]\\ =\sum_{d|m}\sum_{0\leq k<m,d|k}f(k)[\frac{k}{d}\bot \frac{m}{d}]\\ =\sum_{d|m}\sum_{0\leq k<\frac{m}d}f(kd)[k\bot \frac{m}{d}]\\ =\sum_{d|m}\sum_{0\leq k<d}f(\frac{km}{d})[k\bot d] \]

Example3(《具体数学》4.63)

证明:满足$a^n+b^n= c^n(n\in\mathbb{N_+},n>2)$的最小的($n$为第一关键字,$c$为第二关键字)一组正整数解(即费马大定理最小的反例)一定满足以下性质:(另外,$n=4$的情况早被证明了无解)

$n\in prime$.
$\exists m\in \mathbb{N_+},a+b=\begin{cases}m^n & n\nmid c\\n^{n-1}m^n&n\mid c\end{cases}$.

首先证明(1),如果$n$是最小的满足条件的数但并不是质数,我们不妨设$n=xy,x>2$,则$(a^y)^x+(b^y)^x=(c^y)^x$,显然这是更小的一组反例,于是(1)得证.

接下来考虑性质(2),注意到$a,b,c$必然两两互质,不然可以两边同时除以一个数构造出更小的解,又注意到: \[ \gcd(a+b,\cfrac{a^n+b^n}{a+b})=\gcd(a+b,(a^{n-1}-a^{n-2}b+...+b^{n-1}))\\ \gcd(a+b,\cfrac{c^n}{a+b})=\gcd(a+b,na^{n-1})\\ \gcd(a+b,\cfrac{c^n}{a+b})=\gcd(a+b,n) \] 如果$\gcd(a+b,n)=1$,那么我们有$(a+b)\bot \cfrac{c^n}{a+b}$.接下来考虑每一个质因子$p$,如果$(a+b)$中有$x$个$p$,$c$中有$y$个$p$,于是$c^n$中有$ny$个$p$,我们自然有:$x=ny$,于是$\exists m\in \mathbb{N_+}$满足$a+b=m^n$.

如果$n\mid (a+b)$,我们就有:$\gcd(a+b,\cfrac{c^n}{a+b})=n$,此时必有$n\mid c$,$n^n\mid c^n$,并且不难发现:$n^k\mid \cfrac{c^n}{a+b}\Leftrightarrow n^{n-k}\mid (a+b)$,由于上面提到的$\gcd$的原因,$\min\{k,n-k\}=1$,显然$k=1$或者$k=n-1$.下面只需要证明$k\ne n-1$.

冷静一下,如果$n|(a+b),n^2\nmid (a+b)$,令$m=a+b$,此时必有: \[ c^n=a^n+(m-a)^n\\ =a^n+(-a)^n+nm(-a)^{n-1}+\frac{n(n-1)}{2}m^2(-a)^{n-2}+\cdots \] 注意到$n$是奇数,$a^n+(-a)^n=0$,而$n^n|c^n\Rightarrow n^3|c^n$,又注意到$n^3|nm^2$,我们把两边对$n^3$取模: \[ 0\equiv nx(-a)^{n-1}\pmod {n^3} \] 注意到若$n^2\nmid m$,则该式子必不成立.

Stern-Brocot 树

Stern-Brocot树是一种可以不重不漏列举有理数的方式,它的构造如下:

一开始,序列中有两个分数:$\cfrac{0}{1}$和$\cfrac{1}{0}$,这里使用了$0$作分母,但我们暂且认为它是正确的,因为这样会出现很多方便的性质.

接下来,不断地对这个序列进行以下操作:在两个相邻的分数$\cfrac{m}{n}$和$\cfrac{m'}{n'}$之间插入一个新分数$\cfrac{m+m'}{n+n'}$.

这么无限构造下去得到的序列满足两个性质:

所得到的分数全都是最简分数.
所得到的分数不重不漏,换句话说,任意非负有理数都在这个序列中出现恰好一次.

我们不妨认为$\cfrac{1}{0}=+\infty$,那么不难发现这么构造序列,所得到的序列一定是单调递增的.

这是因为如果我们有$\cfrac{m}{n}<\cfrac{m'}{n'}$,那么我们一定有:$\cfrac{m}{n}<\cfrac{m+m'}{n+n'}<\cfrac{m'}{n'}$,其中$n,n',m,m'\geq0$,这一点不难验证.

而正因为如此,我们可以证明所得到的所有分数不重.

然后,如果当前所得到的序列中有两个数$\cfrac{m}{n}$和$\cfrac{m'}{n'}$相邻,则$m'n-mn'=1$,这一点不难通过数学归纳证明.而根据裴蜀定理,显然$m\bot n$且$m'\bot n'$.

我们最后需要证明任意非负有理数都可以通过这个序列构造出来,考虑类似二分的方法构造.换句话说,我们有两个序列中的分数$\cfrac{m}{n}$和$\cfrac{m'}{n'}$,要构造的有理数为$\cfrac ab$且满足$\cfrac{m}n<\cfrac a b<\cfrac {m'}{n'}$.

我们考虑判断$\cfrac{m+m'}{n+n'}$与$\cfrac{a}{b}$的大小关系,这样就可以类似二分的方法一直往下找下去.

问题在于为什么我们最后一定可以找到这个数呢?如果我们一直找不到这个数,意味着无论我们怎么做,都有$\cfrac{m}n<\cfrac a b<\cfrac {m'}{n'}$成立,而这也就意味着$an-bm\geq 1\and bm'-an'\geq 1$,处理一下不等式并合并,我们有$(m'+n')(an-bm)+(n+m)(bm'-an')\geq n+m+n'+m'$.

化简这个式子得到$a+b\geq m'+n'+m+n$,而我们在操作过程中$m,n,m',n'$显然会有两个数不变,另外两个数变大,因此迟早会大于$a+b$,也就意味着这个数迟早会被找到.

之所以称其为”树”,则是因为我们如果每次都在任意两个数之间插入一个数,然后将进行若干次操作得到的序列放到二叉搜索树上,会得到一些很好的性质,譬如一个数是由它所有祖先中最大的小于它的数和最小的大于它的数生成的,以及关于根中心对称的两点互为倒数.

另外,如果我们定义法里级数$\mathcal{F}_n$表示所有在$[0,1]$范围内且分母小于等于$n$的最简分数的集合.不难发现,$\mathcal{F}_n$对应着整棵树的一棵子树的一部分.而$\mathcal{F}_n$可以由$\mathcal{F}_{n-1}$得到,只需要判断$\mathcal F_{n-1}$中每两个相邻数能否生成一个满足条件的数即可.

我们回到它的树形态上,如果我们定义$\cfrac 1 1$为这棵二叉搜索树的根,那么每个有理数显然都可以表示为从根到它的一个$LR$序列,表示从根向下搜索时每一步向左走还是向右走.特别地,我们定义根的序列为$I$.

不难发现,通过这样的操作,我们将每一个非负有理数都对应到了一个$LR$序列.

那么我们来考虑第一个问题:已知$LR$序列如何求这个数.

我们可以设当前点是$x$,且它由$y$和$z$生成,其中$y<x<z$,那么不难发现它的右儿子由$x$和$z$生成,左儿子由$y$和$x$生成.

那么我们显然可以使用记录$y$和$z$的方式,反复迭代求得答案.注意$x$是可以通过$y$和$z$求得的,因此没有必要存储.

而这一过程可以简化为矩阵运算:

我们令$y=\cfrac{m}n$,$z=\cfrac{m'}{n'}$,$S=\begin{bmatrix}n&n'\\m&m'\end{bmatrix}$,$f(S)=\cfrac{m+m'}{n+n'}$.

那么不难发现它的每一次操作只需右乘一个变换矩阵即可.

其中:$L=\begin{bmatrix}1&1\\0&1\end{bmatrix},R=\begin{bmatrix}1 &0\\1&1\end{bmatrix}$.

使用数学归纳不难证明:

$L^k=\begin{bmatrix}1&k\\0&1\end{bmatrix},R^k=\begin{bmatrix}1 &0\\k&1\end{bmatrix}$.

至于已知数字求它的序列表示,首先可以直接在树上搜索.

而如果要脱离树,我们仍然可以回到矩阵上,意识到$f(RS)=f(S)+1$,再加上关于根中心对称两点互为倒数的性质,我们可以推导出以下法则:

如果$m>n$,那么$f(RS)=\cfrac{m}{n}\Leftrightarrow f(S)=\cfrac{m-n}{n}$.

如果$m<n$,那么$f(LS)=\cfrac{m}n\Leftrightarrow f(S)=\cfrac{m}{n-m}$.

借助这一点,我们就可以求一个数的$LR$序列表示了.

在某些情形下,这种表示可以解决二进制下某些分数无法精确表示的问题.

升幂引理

形式一

对于素数$p$,$p\nmid x,p\nmid y$,对于满足$\gcd(n,p)=1$的$n$:

若$p|(x-y)$,则$v_p(x^n-y^n)=v_p(x-y)$.
若$p|(x+y)$,$n$是奇数,则$v_p(x^n+y^n)=v_p(x+y)$.

考虑(1)的证明,由于$p|(x-y),x\equiv y\pmod p$,因此$\sum_{k=0}^{n-1}x^ky^{n-1-k}\equiv nx^{n-1}\ne 0\pmod p$.有次方差公式,显然.

(2)类似.

形式二

对于奇素数$p$,$p\nmid x,p\nmid y$:

若$p|(x-y)$,则$v_p(x^n-y^n)=v_p(x-y)+v_p(n)$.
若$p|(x+y)$,$n$是奇数,则$v_p(x^n+y^n)=v_p(x+y)+v_p(n)$.

和形式一的证明完全类似.

同余

如果$a\mod m=b\mod m$,我们称$a$和$b$关于模$m$同余,记作$a\equiv b(\mod m)$.

根据同余的定义,若$a,b,c,d,k\in \mathbb{Z}$,$n,m\in\mathbb{N_+}$,我们有以下性质:

$a\equiv b\pmod m\Leftrightarrow a-b=km$.
$a\equiv b\pmod m\and c\equiv d\pmod m\Rightarrow a+c\equiv b+d\pmod m$.
$a\equiv b\pmod m\and c\equiv d\pmod m\Rightarrow ac\equiv bd\pmod m$.
$a\equiv b\pmod m\Rightarrow a^k\equiv b^k\pmod m$.
$ad\equiv bd\pmod m\Leftrightarrow a\equiv b\pmod m,m\bot d$.
$ad\equiv bd\pmod {md}\Leftrightarrow a\equiv b\pmod m,d\ne 0$.
$ad\equiv bd\pmod m\Leftrightarrow a\equiv b\pmod {\cfrac{m}{\gcd(m,d)}}$.
$a\equiv b\pmod {md}\Rightarrow a\equiv b\pmod m,d\ne 0$.
$a\equiv b\pmod m\and a\equiv b\pmod n\Leftrightarrow a\equiv b\pmod {lcm(n,m)}$.

我们考虑第五条的证明:由于$m\bot d$,则根据扩展欧几里得算法,可以求得一个数$d'$满足$dd'+mm'=1$,也就是$dd'\equiv 1(\mod m)$,那么如果我们有$ad\equiv bd(\mod m)$,只需要两边同时乘以$d'$就可以得到右边.值得一提的是,我们通常称$d'$是$d$在模$m$意义下的逆元,记作$inv(d,m)$或$d^{-1}$.

逆元有一种线性预处理的求法:

考虑$1\leq i\leq n$,设$p=ki+r$,则有$ki+r\equiv 0(\mod p)$,则有$kr^{-1}+i^{-1}\equiv 0(\mod p)$.

于是有$i^{-1}\equiv -kr^{-1}(\mod p)$,即$i^{-1}\equiv -\lfloor\cfrac{p}{i}\rfloor\times r^{-1}(\mod p)$.

现在,我们给出一个结论:数列$0\mod m,n\mod m,2n\mod m,...,(m-1)n\mod m$在排序去重后恰好为数列$0,d,2d,...,m-d$,$d=\gcd(n,m)$,而且其中每个数字在原数列中恰好出现了$d$次.

恰好出现$d$次是好证明的:考虑$jn\equiv kn(\mod m)$可以推导出$j\equiv k(\mod \cfrac{m}d),d=\gcd(n,m)$,则显然这些数是一个序列复制$d$次得到的.

由上,我们要证明$kn\mod m$一定是$d$的倍数.不难发现$kn\mod m=dk\cfrac{n}d(\mod \cfrac m d d)=d(\cfrac{kn}d\mod \cfrac{m}d)$.

接下来,不妨假设$n\bot m$,并在此条件下证明$0\mod m,n\mod m,2n\mod m,...,(m-1)n\mod m$两两不同即可.而由于$n\bot m$,则$kn\equiv jn(\mod m)$的充分必要条件是$k\equiv j(\mod m)$,因此它们显然两两不同.

Example(《具体数学》4.31)

$n$进制下,各位数字之和是$m$的倍数,则这个数是$m$的倍数的充分必要条件是?

令$a_i$表示这个数字在$n$进制下的第$i$位,则这条性质也就是: \[ \sum_{i=0}a_in^i\equiv 0\pmod m\Leftrightarrow\sum_{i=0}a_i\equiv 0\pmod m \] 不难发现,当$n\equiv 1\pmod m$时,满足该性质.

威尔逊定理

$(p-1)!\equiv \begin{cases} -1(\mod p)&p\in prime\\ 2(\mod p)&p=4\\ 0(\mod p)&other \end{cases}$

证明:

当$p$为质数时，考虑对于$a$和$b=a^{-1}(\mod p)$,若$a=b$,此时可证明$a=1$或$a=p-1$(需要用到下面独立剩余知识).

如果$a\ne b$那么一定可以在$[1,p-1]$找到一对数,它们相乘为$1$.原因是若$a_1\ne a_2$,那么$a_1^{-1}\ne a_2^{-1}$.

若$p$不是质数,则设$p=ab$,当$a\ne b$时,由于$a,b\leq p$,因此$(p-1)!$一定是$p$的倍数.

若$a=b$,除非$p=4$,不然一定能在$[1,p-1]$里找到$a$和$2a$,此时$(p-1)!$也是$p$的倍数.

另外,当$p$是奇质数的时候,威尔逊定理可以写成如下形式: \[ \prod_{k=1}^{\frac{p-1}{2}}k(p-k)\equiv -1\pmod p\\ \prod_{k=1}^{\frac{p-1}2}-k^2\equiv -1\pmod p\\ (-1)^{\frac{p-1}{2}}((\cfrac{p-1}{2})!)^2\equiv -1\pmod p \]

另外,通过以上推导过程,不难发现威尔逊定理还可以写成: \[ (p-2)!\equiv \begin{cases} 1(\mod p)&p\in prime\\ 2(\mod p)&p=4\\ 0(\mod p)&other \end{cases} \]

Example1(《具体数学》4.48)

求$\prod_{1\leq n<m,n\bot m}n\pmod m\\$.

首先,类似威尔逊定理的推导,不难注意到这个式子也就等价于: \[ \prod_{1\leq n<m,n^2\equiv 1\pmod m}n\pmod m \] 首先考虑满足$n^2\equiv 1\pmod m$的$n$满足什么性质,根据我们在二次剩余的推导,先考虑$2\nmid m$的情况,此时我们将$m$分解为了若干个形如$p^k$的质因数的乘积,对于每个$p^k$作为模数时,$n$有两个解:$1$和$p^k-1$.

当$m=p^k$的时候,显然答案就是$-1$.

不然,由于此时有很多解,我们考虑设答案为$ans$并对于每个$p^k$求出$ans $的答案,再使用中国剩余定理合并.不难发现只要$m$有多个不同的质因子,那么中国剩余定理合并的时候,一定会有偶数个$n$(事实上,假设$m$有$a$个质因子,那么有$2^{a-1}$个这样的$n$)满足$n\equiv -1\pmod {p^k}$,也有同样数目的$n$满足$n\equiv 1\pmod {p^k}$.那么此时的$ans\equiv 1\pmod {p^k}$.多次合并后的$ans$显然还是$1$.

至于$2\mid m$的情况并没有麻烦很多,当$2\mid m\and 4\nmid m$,显然有没有这个$2$作为质因子都一样.当$4\mid m\and 8\nmid m$,这个质因子和其它质因子并没有多少区别.

于是我们最后得到结论: \[ \prod_{1\leq n<m,n\bot m}n\equiv \begin{cases} -1\pmod m&m=p^k\or m=2p^k\or m=4,p\in prime\and p\ne 2\\ 1\pmod m&other\\ \end{cases} \]

Example2(《具体数学》4.40)

如果我们设$n=\sum_{k\geq 0}a_kp^k$,求证:$\cfrac{n!}{p^{\varepsilon_p(n!)}}=(-1)^{\varepsilon_p(n!)}\prod_{k\geq 0}a_k!\pmod p$.

证明考虑数学归纳:如果$n\rightarrow n+1$的过程中没有发生进位,那么该公式显然成立.

如果发生进位了,假设进到了第$k$位,第$k$位原本是$w$,现在是$w+1$,那么要证其对于$n+1$成立,即证明下式成立: \[ \cfrac{n!(n+1)}{p^{\varepsilon_p(n!)+k}}=(-1)^{\varepsilon_p(n!)+k}(w+1)!\prod_{i\geq k+1}a_i!\pmod p \] 考虑$(p-1)\equiv -1\pmod p$,于是上式也即: \[ \cfrac{n!(n+1)}{p^{\varepsilon_p(n!)+k}}=(-1)^{\varepsilon_p(n!)}(w+1)\prod_{i\geq 0}a_i!\pmod p\\ \cfrac{n!}{p^{\varepsilon_p(n!)}}\cfrac{n+1}{p^k}=(-1)^{\varepsilon_p(n!)}(w+1)\prod_{i\geq 0}a_i!\pmod p\\ \cfrac{n!}{p^{\varepsilon_p(n!)}}(w+1)=(-1)^{\varepsilon_p(n!)}(w+1)\prod_{i\geq 0}a_i!\pmod p \] 于是化到$n$的情况,于是$n+1$时该式子成立.

Example3(《具体数学》4.53)

求所有满足$n|\lceil\cfrac{(n-1)!}{n+1}\rceil$的整数$n$.

首先这个形式看上去就是威尔逊定理的形式,所以第一步我们先暴力验证$n\in[1,4]$的答案,注意到此时当且仅当$n=1$时成立.接下来我们尝试找到$n\geq 5$时的解.

考虑当$n+1\in prime$时,根据威尔逊定理,要求化为:$n\mid\cfrac{(n-1)!+n}{n+1}$.注意到此时$n$一定不是质数,又因为$n\bot (n+1)$,于是要求化为$n\mid {(n-1)!+n}$,显然成立.

当$n+1\notin prime$时,要求则化为$n\mid \cfrac{(n-1)!}{n+1}$.当$n\in prime$时,显然不成立.反之显然成立.

于是要么$n=1$,要么$n\geq 5\and n\notin prime$.

费马小定理

$n^{p-1}\equiv 1(\mod p),n\bot p,p\in prime$.

我们有: \[ \prod _{k=1}^{p-1}kn\equiv \prod _{k=1}^{p-1}(kn\mod p)(\mod p)\\ n^{p-1}(p-1)!\equiv (p-1)!(\mod p) \] 根据威尔逊定理,显然可以推得费马小定理.

根据费马小定理,我们可以考虑证明一个结论:$n^{p^k}\equiv n^{p^{k-1}}(\mod p^k)$.

由于$n^{p-1}\equiv 1(\mod p)$,那么我们有$n^p\equiv n(\mod p)$,也即$\exist q\in\mathbb{Z}$满足$n^p=n+pq$,不断两边取$p$次方即可得到上述结论.

另外,费马小定理还可以如下证明:

考虑证明$n^p\equiv n\pmod p$,也就是要证明$(\sum_{i=1}^n1)^p\equiv n\pmod p$.

注意到根据多项式定理,$(\sum_{i=1}^n1)^p=\sum_{\sum a=p}\cfrac{p!}{a_1!...a_n!}$.而如果$\max\{a\}\ne p$,则后面的式子在$\mod p$意义下显然为$0$,不然,考虑$\max\{a\}=p$的序列一共会出现$n$次且每次对答案的贡献都是$1$,自然有$n^p\equiv n(\mod p)$.

Example1(《具体数学》4.41)

求证:如果质数$p$满足$p\equiv 3\pmod 4$,则不存在整数$n$满足$p|(n^2+1)$;如果其满足$p\equiv 1\pmod 4$,则一定存在一个整数$n$满足条件.

先考虑证明前半部分,如果存在这样一个整数$n$,考虑$p|(n^2+1)$也就等价于$n^2\equiv -1\pmod p$,则$n^4\equiv 1\pmod p$.显然$p\bot n$,根据费马小定理,我们有$n^{p-1}\equiv 1\pmod p$,也就有$n^{p+1}\equiv -1\pmod p$.

而由于$p\equiv 3\pmod 4$,所以$4|(p+1)$,所以$n^{p+1}\equiv 1\pmod p$,不符,因此一定不存在.

反之,考虑威尔逊定理的变形$\prod_{k=1}^{\frac{p-1}2}-k^2\equiv -1\pmod p\\$.由于$p-1\equiv 0\pmod 4$,所以这个式子也就等价于$\prod _{k=1}^{\frac{p-1}2}k^2\equiv -1\pmod p$,也就是$((\cfrac{p-1}{2})!)^2\equiv -1\pmod p$,这就是一个解.

Example2(《具体数学》4.46)

求证:如果$n>1$,则$2^n\ne 1\pmod n$.

如果$n$是质数,根据费马小定理,显然得证.

不然,设$n=pq$,且$p$是$n$的最小质因子,若$2^{n}\equiv 1\pmod n$,则$2^n\equiv 1\pmod p$.

若$p=2$,显然不成立.不然,有$2^{p-1}\equiv 1\pmod p$,由于$(p-1)\bot n$,则$2^{\gcd(p-1,n)}\equiv 2\equiv 1\pmod p$,显然不成立.

另外,上面的过程显然可以推广为:

如果$n>1$,则对于任意质数$p$,$p^n\ne 1\pmod n$.

中国剩余定理(crt)

对于方程组$x\equiv a_i(\mod m_i)$,其中$m_i$两两互质,求$x$.

令$m=\prod^k_{i=1}m_i$,设$M_i=\cfrac{m}{m_i}$,$N_i$是$M_i$在$\mod m_i$意义下逆元.

则$x\equiv \sum^k_{i=1}M_iN_ia_i(\mod m)$.

中国剩余定理的证明类似拉格朗日插值:

由于$x$在$\mod m_i$意义下,$\sum$中枚举的所有不等于$i$的项都会成$0$，等于$i$的项会成$a_i$.

考虑每次合并两项，显然有:$a=a_1+(a_2-a_1)\times m_1\times inv(m_1,m_2)$,$m=m_1m_2$.

中国剩余定理的本质是一个环同构$\varphi:\Z/m_1m_2\Z\rightarrow (\Z/m_1\Z)\times (\Z/m_2\Z)$,当$m_1\bot m_2$.

由于映射两边都是大小相同的有限环,所以只需证明它是单射就行.而容易发现$\ker \varphi=\{[1]\}$.

下面的扩展中国剩余定理亦然同理,用一下裴蜀定理证明映射两边的有限环大小相等,再注意到$|\ker \varphi|=1$.

扩展中国剩余定理(excrt)

对于方程组$x\equiv a_i(\mod m_i)$,若$m_i$两两不互质.

我们考虑每次合并两个方程:$\begin{cases} x\equiv a_1(\mod m_1)\\ x\equiv a_2(\mod m_2) \end{cases}$ 那这个方程组等价于:$\begin{cases} x=k_1m_1+a_1\\ x=k_2m_2+a_2 \end{cases}$ 合并上下方程,有: \[ k_1m_1+a_1=k_2m_2+a_2\\ a_2-a_1=k_1m_1-k_2m_2 \] 设$g=\gcd(m_1,m_2)$,显然若$g\nmid (a_2-a_1)$,方程无解.

不然,有: \[ \frac {a_2-a_1}g=k_1\frac {m_1}{g}-k_2\frac{m_2}{g}\\ k_1\frac{m_1}{g}=k_2\frac {m_2}g+\frac {a_2-a_1}g\\ k_1\frac{m_1}g\equiv \frac {a_2-a_1}{g}(\mod \frac {m_2}g)\\ \] 令$inv(a,p)$表示$a$在$\mod p$意义下的逆元,有: \[ k_1\equiv inv(\frac {m_1}{g},\frac {m_2}g)\frac{a_2-a_1}{g}(\mod \frac {m_2}g)\\ k_1=inv(\frac{m_1}g,\frac{m_2}g)\frac{a_2-a_1}g+k_3\frac{m_2}g\\ \] 带回第一个方程: \[ x=m_1(inv(\frac{m_1}g,\frac{m_2}g)\frac{a_2-a_1}g+k_3\frac{m_2}g)+a_1\\ x\equiv m_1inv(\frac{m_1}g,\frac{m_2}g)\frac{a_2-a_1}g+a_1(\mod \frac{m_1m_2}g) \]

Example1([NOI2018]屠龙勇士)

考虑拿个set之类的维护,然后问题转化为求: \[ \begin{cases} b_1x\equiv a_1(\mod m_1)\\ b_2x\equiv a_2(\mod m_2)\\ ...\\ b_nx\equiv a_n(\mod m_n) \end{cases} \] 的一个$x$的最小解.

对于一个式子$b_ix\equiv a_i\pmod {m_i}$,设$g=\gcd(b_i,m_i)$,那么若$g\nmid a_i$,显然无解;不然,我们有:$\cfrac{b_i}{g}x\equiv \cfrac{a_i}g\pmod {\cfrac{m_i}{g}}$,而$\cfrac{b_i}{g}\bot \cfrac{m_i}{g}$,可以求逆元.

Example2([CF571E]Geometric Progressions)

首先分解质因子,这样问题转化为判断等差数列中是否出现.我们随便挑一个数列,假设这个数列中第$x$个数字是答案,显然最小化$x$即可.

但是直接对所有质因子做excrt复杂度不可接受.我们考虑如果对于质因子$p$,$\exists i,j\in[1,n],i\ne j$有$p|b_j,p\nmid a_i,p\nmid b_i$,显然无解.如果有$p|b_j,p|a_i,p\nmid b_i$,显然要么无解,要么有唯一解,而且可以快速求出唯一解是谁,直接验证就行.

这样,我们就保证了所有需要做excrt的质因子必然全部出现,容易发现这样的质因子数量很少.

二次剩余

求方程$x^2=k(\mod m)$的解.

我们先考虑一个特殊情况:$k=1$,$m=p^k,p\in prime$.

那么也就相当于求方程$(x-1)(x+1)\equiv 0(\mod p^k)$.

如果$p>2$,那么显然$x-1$和$x+1$只有一个能被$p^k$整除,所以有$x=\pm 1$.

如果$p=2$,那么显然$x-1$和$x+1$有一个能被$2$整除但不能被$4$整除,另一个能被$2^{k-1}$整除,如果$k=1$时,显然只有一个解.当$k=2$时,同上.反之,有$x=\pm 1$或$x=2^{k-1}\pm 1$.考虑一个性质:$(2k+1)^2\equiv 1(\mod 8)$.

那么如果:$k=1,m\in\mathbb{N_+}$,也是一样的.先把$m$作质因数分解,然后再用中国剩余定理合并,那么显然不同质数的解会累乘到总的解上,若$m$有$r$个不同大于$2$的质因子,总的解的个数是$2^r$.而如果考虑$p=2$的情况,$m$有$r$个不同的质因子,则解的个数为$2^{r+[8|m]+[4|m]-[2|m]}$.

下面开始讲正经的二次剩余.

我们称$a$是$p$的二次剩余,当且仅当$\exists b,b^2\equiv a\pmod p$并且$a\ne 0\pmod p$,这里的$p$是奇素数,如果$a$不是$p$的倍数且$\nexists b,b^2\equiv a\pmod p$,则称为二次非剩余.我们引入勒让德符号来表示这个东西: \[ \left(\frac{a}{p}\right)=\begin{cases}1&a是二次剩余\\0&a\equiv 0\pmod p\\-1&a为二次非剩余\end{cases} \] 那么这玩意怎么求呢?我们有欧拉判别准则: \[ \left(\frac{a}{p}\right)\equiv a^{\frac{p-1}{2}}\pmod p \] 先证明个引理:若$g$为$\bmod p$意义下的原根,且$a\equiv g^k$,那么$x^2\equiv a\pmod p$有解的充要条件是$k$是偶数.

充分性显然,而必要性,我们考虑费马小定理:$g^{p-1}\equiv 1\pmod p$,而$p-1$是偶数,因此无论如何奇偶性都不会变.

接下来证明欧拉判别准则: \[ g^{p-1}\equiv 1\pmod p\\ g^{p-1}-1\equiv 0\pmod p\\ (g^{\frac{p-1}{2}}+1)(g^{\frac{p-1}{2}}-1)\equiv 0\pmod p\\ g^{\frac{p-1}{2}}\equiv -1\pmod p\\ a^{\frac{p-1}{2}}=(g^k)^{\frac{p-1}{2}}=(g^{p-1})^{\frac{k}{2}} \] 于是得证.另外通过这个证明过程,我们可以发现$[1,p-1]$中有正好一半的数是二次剩余,我们还能得知$x^2\equiv a\pmod p$的解的数量是$\left(\frac{a}{p}\right)+1\\$.

Example1([CF1091G]New Year and the Factorisation Collaboration)

考虑随机一个$x$,令$x'=\sqrt{x^2}\pmod n$,如果$x'=x$则放弃这次询问,不然自然有$(x'-x)(x'+x)\equiv 0\pmod n$.

$\forall p|n,p\in prime$,注意到一定满足$p|(x'-x)$或$p|(x'+x)$,我们可以多做几次,可以理解为这样将$n$随机分割了.

Example2(qoj5021)

整个题就强调一个字:双射!

先把模数质因数分解.

从头开始看,这种多元组计数肯定要一点一点确定,我们考虑固定$(a,a')$求解$(b,b')$,这个时候发现只要$(a,a')$不全为$0$,那么就有$p$组$(b,b')$满足条件,这个可以通过移项求逆元发现.发现这个全为$0$的条件很烦,我们先把它处理掉.

显然只有$r=0$会出现这种情况,讨论一下$(a,a')$全为$0$或$(b,b')$全为$0$的情况,简单分类讨论可以得到共有$2p^3+p^2-2p$种方案.

好了,困难的部分被我们解决了,不过这样我们需要多讨论一下$r$是否等于$0$,不过问题不大.

先考虑$r=0$的情况:

注意到此时固定$(a,a')$会有$p-1$组(有一组全$0$)$(b,b')$满足条件,此时有方程$\begin{cases}ac+a'c'\equiv 0\pmod p\\bc+b'c'\equiv 0\pmod p\end{cases}$.显然若$(b,b')\equiv k(a,a')$,那么该方程有$p$组解,不然只有一组解.而前者相当于$(a,a')$满足$ka^2+ka'^2\equiv 0$,我们设$C_k$是方程$a^2+a'^2\equiv k\pmod p$的解的数量,把上面的全部加起来,答案是: \[ (C_0-1)(p-1)p+((p^2-1)(p-1)-(C_0-1)(p-1)) \] 化简一下得到:$(C_0-1)(p-1)^2+p^3-p^2-p+1$.

再考虑$r\ne 0$的情况:

注意到此时不可能有全为$0$的二元组了.所以固定$(a,a')$的话,$(b,b')$共有$p$组解,此时有方程$\begin{cases}ac+a'c'\equiv r\pmod p\\bc+b'c'\equiv r\pmod p\end{cases}$.

若$(b,b')\equiv k(a,a')$,显然当$k=1$时有$p$组解,否则无解,此时$a^2+a'^2\equiv r\pmod p$.

不然有唯一解.

而$(b,b')=k(a,a')$的方案有多少呢,显然是$\sum_{k=1}^{p-1}C_{\frac{r}{k}}=\sum_{k=1}^{p-1}C_k=p^2-C_0$,这里用到了这篇题解的第一个双射,$[1,p-1]/k\mapsto [1,p-1]$.

于是这里的答案就是: \[ C_rp+((p^2-1)p-(p^2-C_0)) \] 化简一下得到$p^3-p^2-p+C_0+C_rp$.

现在的问题是如何求$C_0,C_r$.

先来技术总结一下,这种多元组计数通常要确定一些数字,然后对另一些数字进行计数,如果确定的那些数字不能进行枚举,那就得进行一些别的操作来在不同的情况下判断数量.

那么$C_r$怎么求呢?考虑$x^2\equiv a\pmod p$的解数为$\left(\frac{a}{p}\right)+1$,我们有: \[ C_r=\sum_{i=0}^{p-1}(\left(\frac{i}{p}\right)+1)(\left(\frac{r-i}{p}\right)+1)\\ =\sum_{i=0}^{p-1}\left(\frac{i(r-i)}{p}\right)+2\sum_{i=0}^{p-1}\left(\frac{i}{p}\right)+p\\ =\sum_{i=1}^{p-1}\left(\frac{\frac{r}{i}-1}{p}\right)+p \] ~~(这是干啥啊)~~

我们来一步一步分析这个式子是怎么得到的:

首先,第一步仍然是枚举其中一个,然后求另一个.然后将整个式子乘开,做一个双射$r-[0,p-1]\mapsto [0,p-1]$就可以合并其中两项,而至于前两项则是根据欧拉判别准则直接将上指标乘起来合并.然后我们发现$\sum_{i=0}^{p-1}\left(\frac{i}{p}\right)=0$,因为$[0,p-1]$中一半是$1$一半是$-1$,又可以发现$i=0$时显然为$0$,$x^2=i(r-i)\Leftrightarrow (\frac{x}{i})^2=\frac{r}{i}-1$,做双射$[1,p-1]\times i^{-1}\mapsto [1,p-1]$.

做到这一步,自然有$C_0=(p-1)\left(\frac{-1}{p}\right)+p$.

而对于$r\ne 0$的时候,我们再做双射$r/[1,p-1]\mapsto [1,p-1]$,于是$C_r=\sum_{i=0}^{p-2}\left(\frac{i}{p}\right)+p=p-\left(\frac{-1}{p}\right)$.

只能说模质数意义下的加法乘法减法以及不含$0$的乘法都是群,而且所有运算都是双射,很牛逼,计数题直接起飞.

不过这题需要特别判断一下$p=2$的情况,也容易,暴力就行.

Example3

求$2^a=3^b+1$和$3^a=2^b+1$的所有解.

先看$2^a=3^b+1$,显然$(2,1)$是一组解.当$y\geq 3$的时候,显然有$3^a+1\equiv 0\pmod 8$,而考虑$3^{2k}\equiv 1\pmod 8$,这自然不可能.

再看$3^a=2^b+1$.显然$(1,1)$和$(2,3)$是两组解.当$b\geq 2$的时候$3^a\equiv 1\pmod 4$,根据欧拉定理知道$a\in \text {even}$,令$a=2k$.自然有$(3^k-1)(3^k+1)=2^b$,这是形如$t(t+2)=2^b$的形式,只有$t=2$是一个解.

BSGS

求$a^x\equiv b(\mod p)$的一组解,其中$p\in prime$且$1\leq p\leq 10^9$.

直接枚举显然是$O(p)$的,非常不合理,考虑如何优化.

求出$s=\lfloor\sqrt{p}\rfloor$,并求出所有$a^i$,其中$i\in [0,s-1]$.

若$x\leq s-1$.则可以直接判断是否被求出来过.

否则,则将$x=x\mod (s-1)$,一直操作直到$x\leq s-1$.

exBSGS

求$a^x\equiv b(\mod p)$的一组解,其中$1\leq p\leq 10^9$.

设$g=\gcd(a,p)$,那么根据膜的性质,原方程即$\frac {a^x} g\equiv \frac b g (\mod \frac p g)$.

显然若$g\nmid b$并且$b\ne 1$,方程定无解.(若$b=1$,那么$x=0$就是一个解)

那么现在的方程就是$a^{x-1}\frac a g\equiv \frac b g(\mod \frac p g)$.

继续进行这个过程,不断求$a$和当前模数的$\gcd$.并将当前模数除以该$\gcd$,这样最后我们得到了方程:

$a^{x-k}\prod_{i=1}^k \frac a {g_i}\equiv \frac b {\prod_{i=1}^k g_i}(\mod \frac p {\prod_{i=1}^k g_i})\\$

不妨设$A=\prod_{i=1}^k \frac a {g_i},B=\frac b {\prod_{i=1}^k g_i},P=\frac p {\prod_{i=1}^k g_i}\\$

那么现在方程就是$a^{x-k}\equiv \frac B A\pmod P$,可以使用BSGS求解.

ps：$p=1$的时候要特判.

原根和阶

阶:找到一个最小的$k$使得$a^k\equiv1(\mod p)$,则称$k$是$a$在膜$p$意义下的阶.

原根:如果$a$在膜$p$意义下的阶是$\varphi(p)$且$a<p$,则称$a$是$p$的一个原根.

若$m$有原根,则$m$一定是$2$,$4$或是$p^a,2p^a$,其中$p\in prime$且$2\nmid p$.

由于对于大部分$m$来说,都存在一个很小的原根,所以在实际应用中只需要暴力找就可以了.

根据阶的定义,我们如果要判断一个$a$不是$p$的原根,只需判断是否$\exists i$使得$a^i\equiv 1(\mod p)$.

而由于$a^{\varphi(p)}\equiv 1(\mod p)$,因此一定有$i|\varphi(p)$,因此只需判断$\varphi(p)$的所有因数,复杂度$O(\sqrt{\varphi(p)})$.

事实上,只需要判断对于$\varphi(p)$的所有质因子$w$,是否有$a^{\frac {\varphi(p)} w}\equiv 1(\mod p)$即可,复杂度$O(\omega (p))$.

Example1

给定$k$,$p$,$a$,求$x^k\equiv a(\mod p)$的所有解,其中$p\in prime$,$1\leq k \leq 10^5$.

考虑求出$p$的原根$g$,得到$g^r\equiv a(\mod p)$,同时由于$x\equiv g^y(\mod p)$,因此原方程变为:$g^{yk}\equiv g^r(\mod p)$.

于是有:$yk\equiv r(\mod p-1)$,即可求解.

Example2(《具体数学》4.47)

证明:如果$\exist n,n^{m-1}\equiv 1\pmod m$,且对于所有满足$p|(m-1)$的$p$都满足$n^{\frac{m-1}{p}}\ne 1\pmod m$,那么$m$是素数.

首先不难发现,$m\in\ prime\Leftrightarrow \varphi(m)=m-1$.

考虑上面的过程中,不可能存在一个数$k$满足$0\leq k<m-1,n^k\equiv 1\pmod m$.因此$\nexists 0\leq i,j<m,i\ne j,n^i\equiv n^j\pmod m$.

根据欧拉定理,$m-1=\varphi(m)$,因此得证.

积性函数

若函数$f(x)$满足$\forall n,m\in \mathbb{N_+},n\bot m$,有$f(1)=1,f(nm)=f(n)f(m)$,则称其为积性函数.若$\forall n,m\in \mathbb{N_+}$,有$f(1)=1,f(nm)=f(n)f(m)$,则称其为完全积性函数.

若函数$g(x)$是积性函数并且有$g(m)=\sum_{d|m}f(d)$,则$f(x)$也是积性函数,证明如下:

不妨考虑数学归纳,首先$g(1)=f(1)=1$.

令$m=m_1m_2,m_1\bot m_2$,则$g(m)=\sum_{d|m}f(d)=\sum_{d_1|m_1}\sum_{d_2|m_2}f(d_1d_2)$.由于归纳假设,此时只有$d_1=m_1\and d_2=m_2$的时候,$f(d_1d_2)$可能不等于$f(d_1)f(d_2)$.

于是有 \[ g(m)=\sum_{d_1|m_1}\sum_{d_2|m_2}f(d_1)f(d_2)-f(m_1)f(m_2)+f(m_1m_2)\\=g(m_1m_2)-f(m_1)f(m_2)+f(m_1m_2) \] 于是$f(m_1)f(m_2)=f(m_1m_2)$.

该命题的逆命题也是同样成立的.有一些常见的积性函数,比如:$id(x)=x$,$I(x)=1$,$\varepsilon(x)=[x=1]$.

Example(《具体数学》4.58)

求:$f(m)=\sum_{d|m}d$是$2$的整数次幂的充分必要条件.

不难发现$f$是一个积性函数,于是考虑$f(p^k)=1+p+p^2+...+p^k$.

当$p=2$的时候,显然不满足条件.

不然,只有$k$是奇数的时候,$f(p^k)$才是一个偶数.

而此时$f(p^k)=(1+p)(1+p^2+p^4+...+p^{k-1})=(1+p)(1+p^2)(1+p^4+...+p^{k-3})$.其是$2$的整数次幂的一个必要条件是$p$是一个梅森素数,而且不难发现只有当$k=1$的时候才满足条件.

于是充分必要条件是:$m$是若干个不同的梅森素数的乘积.

狄利克雷卷积

$f*g=\sum_{d|n}{f(d)g(\cfrac n d)}$.

不难证明狄利克雷卷积满足:

交换律:$f*g=g*f$.
结合律:$f*(g*h)=(f*g)*h$.
分配律:$f*(g+h)=f*g+f*h$.
若$f,g$是积性函数,则$f*g$也是积性函数.

考虑第四条的证明: \[ f*g(nm)=\sum_{d|(nm)}f(d)g(\cfrac{n}d)\\ =\sum_{c|n}\sum_{d|m}f(cd)g(\cfrac{nm}{cd})\\ =\sum_{c|n}\sum_{d|m}f(c)f(d)g(\cfrac{n}{c})g(\cfrac{m}{d})\\ =(f*g(n))\times (f*g(m)) \]

$\forall f,f(1)\ne 0$,$\exists f^{-1}$,$f*f^{-1}=\epsilon$.

构造$g(x)$满足$f(1)g(x)=\epsilon(x)-\sum_{d|x,d\ne 1}f(d)g(\frac{x}{d})$显然就是满足条件的.

积性函数的逆元也是积性函数.

欧拉函数

定义欧拉函数$\varphi(m)$为所有满足$1\leq n\leq m\land n\perp m$的$n$的个数.

令$m=m_1m_2$,其中$m_1\bot m_2$.由于若$n\bot m_1,n\bot m_2$,显然有$(n\mod m_1)\bot m_1$且$(n\mod m_2)\bot m_2$,则根据中国剩余定理,不难有$\varphi(m)=\varphi(m_1)\varphi(m_2)$,也即$\varphi(x)$是积性函数.

若$n=\prod^{k}_{i=1}p_i^{a_i}$,则:

$\varphi(n)=\prod^k_{i=1}\varphi(p_i^{a_i})=\prod^k_{i=1}{p_i^{a_i}-p_i^{a_i-1}}=\prod^k_{i=1}{p^{a_i-1}(p_i-1)}$.

考虑改变枚举方式,因为$n=\prod_{p|n}p^{a_p}$,则:$\varphi(n)=\prod_{p|n}{p^{a_p-1}(p-1)}=\prod_{p|n}{(p^{a_p}\times \cfrac{p-1}{p})}=n\times\prod_{p|n}\cfrac{p-1}{p}$.

我们考虑一个事实:现在有$m$个不同的分数$\cfrac{k}m,k\in[1,m]$,这些分数进行约分后,它们的分母即$m$的若干因数,而它们的分子就是与这些因数互质的数,同时这些数的个数总共是$m$个,我们可以得到:$\sum_{d|m}\varphi(d)=m$.

上面这个结论还有另一种证明方法:

由于$\varphi$是积性函数,若$n\ne1$,设$n=\prod_{i=1}^kp_i^{q_i}$,则$\varphi(n)=\prod_{i=1}^k\varphi(p_i^{q_i})$,则有: \[ \sum_{d|n}\varphi(d)=\sum_{w_1=0}^{q_1}\sum_{w_2=0}^{q_2}......\sum_{w_k=0}^{q_k}{\varphi(p_1^{w_1})\varphi(p_2^{w_2})......\varphi(p_k^{w_k})}\\ \] 而$\varphi(p^q)=p^q-p^{q-1}$,于是有$\sum_{i=1}^{q_i}{(p_x^i-p_x^{i-1})}=(p_x^{q_x}-1)$,则有$\sum_{i=0}^{q_x}\varphi(p_x^{i})=p_x^{q_x}$.

则原式等于$\prod_{i=1}^kp_i^{q_i}=n$.

和法里级数的关系

我们考虑之前提到的法里级数$\mathcal{F}_n$,令$\Phi(x)=\sum_{1\leq k\leq x}\varphi(k)$,那么$\mathcal{F}_n$的个数显然是$\Phi(x)+1$.

接下来我们思考如何计算$\Phi(x)$.事实上,我们有$\sum_{d=1}^n\Phi(\lfloor\cfrac{n}d\rfloor)=\cfrac{1}2(n+1)n$.这里的证明是:考虑满足$0\leq a<b\leq n$的分数$\cfrac{a}{b}$共有$\cfrac{1}2n(n+1)$个,而如果我们枚举$d=\gcd(a,b)$,那么显然右边也等于这些分数个数,于是得证.

而事实上,如果我们用$n=\lfloor x\rfloor$来带入上面的式子,可以得到$\sum_{d=1}\Phi(\cfrac{x}d)=\cfrac{1}2\lfloor x\rfloor\lfloor1+x\rfloor$.

根据第三种莫比乌斯反演的形式,我们有:$\Phi(x)=\cfrac1 2\sum_{1\leq d}\mu(d)\lfloor\cfrac{x }d\rfloor\lfloor\cfrac x d+1\rfloor$.

麦克马洪和式

考虑这个问题:我们现在有$m$种颜色,要对一个长度为$n$的圆环进行染色,旋转后相同算一种方案,求方案数.

我们先设答案为$N(n,m)$,并将这些答案全部列举出来,然后将它们进行旋转,进行$n-1$次.这样我们就得到了$nN(n,m)$个圆环,但是这些圆环是有重复的.

那么我们显然有: \[ nN(n,m)=\sum_{a_0a_1...a_{n-1}}\sum_{0\leq k<n}[a_0a_1...a_{n-1}=a_k...a_{n-1}a_0...a_{k-1}]\\ =\sum_{0\leq k<n}\sum_{a_0a_1...a_{n-1}}[a_0a_1...a_{n-1}=a_k...a_{n-1}a_0...a_{k-1}] \] 接下来我们只需要知道,当已知$k$的时候,右边和式的贡献是多少.显然此时有$a_i=a_{(i+k)\mod n}$,也就是$a_i=a_{(i+kl)\mod n}$,此时答案为$m^{\gcd({n,k})}$.

为啥答案为$m^{\gcd(n,k)}$呢?我们考虑这一定会不断在$a$中取数,那么会取多少数呢?显然会取$x-1$个数,其中$i+xk=i+yn$,不难解得此时$x=\frac{n}{\gcd(k,n)}$,因此一共有$\gcd(n,k)$个轨道.

也就是说:$nN(n,m)=\sum_{0\leq k<n}m^{\gcd(n,k)},N(n,m)=\cfrac{1}n\sum_{0\leq k<n}m^{\gcd(n,k)}\\$.

如果我们对这个式子进行化简: \[ N(n,m)=\cfrac{1}{n}\sum_{d|n}m^d\sum_{0\leq k<n}[d=\gcd(n,k)]\\ =\cfrac{1}{n}\sum_{d|n}m^d\sum_{d|k,k<n}[\cfrac{k}{d}\bot \cfrac{n}{d}]\\ =\cfrac{1}{n}\sum_{d|n}m^d\sum_{0\leq k<\frac{n}d}[k\bot \cfrac{n}d]\\ =\cfrac{1}{n}\sum_{d|n}\varphi(d)m^{\frac{n}{d}}. \] 这个式子被称为麦克马洪公式.

另外,如果我们考虑$n|(\sum_{d|n}\varphi(d)n^{\frac{n}{d}})$这件事的证明,考虑如果$n=p^k$,那么根据费马小定理,显然可证明.

而由于$\varphi(x)$是积性函数,令$n=n_1n_2,n_1\bot n_2$,有: \[ \sum_{d|n}\varphi(d)n^{\frac{n}d}=\sum_{d_1|n_1,d_2|n_2}\varphi(d_1d_2)n^{\frac{n_1n_2}{d_1d_2}}\\ =\sum_{d_1|n_1}\varphi(d_1)(\sum_{d_2|n_2}\varphi(d_2)(n^{\frac{n_1}{d_1}})^{\frac{n_2}{d_2}}) \] 我们可以通过数学归纳来证明.

Burnside定理

现在让我们来进行一些抽象代数的计算.

置换群:运算$(a_1,a_2,...,a_k)$表示将$a_1$放到$a_2$位置…把$a_i$放到$a_{i+1}$的位置…把$a_k$放到$a_1$的位置,而幺元$e=(1)(2)(3)...(n)$.

由麦克马洪和式的证明,我们不难推导出Polya定理:设要对$n$个元素用$m$种颜色染色,若通过某种旋转得到的染色方案算同一种,考虑旋转一定是一种置换,则本质不同的染色方案数$=\cfrac{\sum_{s\in S}m^{\eta(s)}}{|S|}$,其中$\eta(s)$表示$s$的轨道数,即有多少组置换.

Example1([HNOI2009]图的同构计数)

首先看到循环同构,第一反应就是Burnside定理.考虑将每条边的状态设为两种:选或不选,那么我们就对点的编号进行置换,然后找到不动边的数量.

我们先考虑对于一个置换,该如何求得它的不动边的数量.考虑置换是一个排列,对它做置换环分解.

现在问题在于置换环内和置换环间要分别求不动点的数量.

先来考虑置换环内:由于是一个置换环,我们假设它的大小是$b$,将这$b$个点排成一个正$b$边形($b$个点的完全图),考虑一个一条边转多少次才能转回来,如果不是$b$是偶数并且这条边正好平分整个多边形的话,显然需要转$n$次,简单判掉特殊情况,发现轨道数量$\lfloor\frac{b}{2}\rfloor$.

接下来考虑置换环外:对于两个置换环间,对于一条边,我们考虑不断做置换,做多少次才能使这条边回归原位置.注意到需要做$lcm(b_1,b_2)$次.而总共有$b_1b_2$条边,于是轨道数量$\frac{b_1b_2}{lcm(b_1,b_2)}=\gcd(b_1,b_2)$.

这样对于一个$k$个环的置换,它的答案就是$\sum_{i=1}^k\lfloor\frac{b_i}{2}\rfloor+\sum_{i=1}^k\sum_{j=i+1}^k\gcd(b_i,b_j)$.

接下来发现本质不同的置换不多,搜出来每个置换环的大小,暴力判断.

欧拉定理

当$a\perp m$时,$a^{\varphi(m)}\equiv 1(\mod m)$.

证明考虑取出$[1,m]$中所有和$m$互质的数,设它们为$b_1,b_2,\cdots,b_{\varphi(m)}$.我们有: \[ \prod _{k=1}^{\varphi(m)}ab_k\equiv \prod _{k=1}^{\varphi(m)}(ab_k\bmod p)(\mod p)\\ a^{\varphi(m)}\prod _{k=1}^{\varphi(m)}b_k\equiv \prod _{k=1}^{\varphi(m)}b_k(\mod p) \]

欧拉定理可以用来求逆元:$a^{\varphi(p)}\equiv 1(\mod p)$,则有$a^{-1}\equiv a^{\varphi(p)-1}(\mod p)$.

扩展欧拉定理

$a^b\equiv a^c(\mod m)$,其中$c= \begin{cases} b\bmod \varphi(m) &a\perp m\\ b &b<\varphi(m)\\ (b\bmod \varphi(m))+\varphi(m) &other \end{cases}$

证明如下:

设$m=\prod^k_{i=1}p_i^{e_i}$,则要证$a^b\equiv a^{(b\mod \varphi(m))+\varphi(m)}(\mod m)$,即证$\forall i$都有$a^b\equiv a^{(b\mod \varphi(m))+\varphi(m)}(\mod p_i^{e_i})$.

分情况讨论:

若$p_i^{e_i}\perp a$,则为普通欧拉定理情况,即证明$\varphi(p_i^{e_i})$是$b-c$的因数.由于$\varphi(p_i^{e_i})$是$\varphi(m)$的因数,而$\varphi(m)$是$b-c$的因数,显然得证.

不然,发现$e_i\leq\varphi(p_i^{e_i})\leq\varphi(m)\leq b$且$\varphi(m)\leq c$,又发现$p_i^{e_i}|a^{e_i}$,所以$p_i^{e_i}|a^b$,$p_i^{e_i}|a^c$,左右两边均为$0$,得证.

######Example1(CF906D Power Tower)

考虑每次暴力做扩展欧拉定理,注意到每次会把$p$变成$\varphi(p)$,如果$p$是奇数,那它下一步会变为偶数,如果$p$是偶数,则下一步至少减半,于是迭代次数是$\log n$级别的.

Example2([六省联考 2017] 相逢是问候)

同上.

Example3(《具体数学》4.54)

求$1000!\pmod {10^{250}}$.

首先,根据前面的例题,不难发现$5^{249}\times 2^{994}\mid (1000!)$.

我们有: \[ 1000!\equiv ans \pmod {10^{250}}\\ \cfrac{1000!}{10^{249}}\equiv \cfrac{ans}{10^{249}}\pmod {10} \] 由于模数现在变成了$10$,考虑$1\times 3\times 3\times 7\times 9\mod {10}=7$,于是我们有: \[ \cfrac{ans}{10^{249}}\equiv 2^{745}\times 7^{100}\pmod {10}\\ \] 而$\varphi(10)=4$,根据扩展欧拉定理: \[ \cfrac{ans}{10^{249}}\equiv 2^{5}\pmod {10}\\ ans\equiv 2\times 10^{249}\pmod {10^{250}} \]

Example1(《具体数学》4.57)

求证:$\sum_{1\leq k\leq n+m}\varphi(k)[(m\mod k)+(n\mod k)\geq k]=nm\\$.

先考虑将条件改为一个更好处理的式子,不难发现: \[ [m\bmod k+n\bmod k\geq k]=\lfloor\cfrac{n+m}{k}\rfloor-\lfloor\cfrac{n}{k}\rfloor-\lfloor\cfrac{m}{k}\rfloor \] 于是接下来我们要处理的式子形如$\sum_{1\leq k\leq n}\varphi(k)\lfloor\cfrac{n}{k}\rfloor\\$.

对其增加枚举量: \[ \sum_{1\leq k\leq n}\varphi(k)\lfloor\cfrac{n}{k}\rfloor=\sum_{1\leq k\leq n}\varphi(k)\sum_{d=1}^{\lfloor \frac{n}{k}\rfloor}1\\ =\sum_{k=1}^n\sum_{d|k}\varphi(d)\\ =\sum_{k=1}^nk=\cfrac{(n+1)n}{2} \] 带入即可证明.

Example2

求$\sum_{1\leq a,b\leq p(p-1)}[a^b\equiv b^a(\mod p)],p\in prime$.

考虑$p\bot (p-1)$,使用中国剩余定理,我们有: \[ \sum_{1\leq a,b\leq p(p-1)}[a^b\equiv b^a(\mod p)]\\ =\sum_{0\leq a,b< p}\sum_{0\leq c,d<p-1}[a^c\equiv b^d(\mod p)]\\ =(p-1)^2+\sum_{1\leq a,b< p}\sum_{0\leq c,d<p-1}[a^c\equiv b^d(\mod p)] \] 后面那部分的答案是: \[ \sum_{1\leq a,b< p}\sum_{0\leq c,d<p-1}[a^c\equiv b^d(\mod p)]\\ =\sum_{1\leq x< p}\sum_{0\leq a,b< p}\sum_{1\leq c,d<p-1}[a^c\equiv x(\mod p)][b^d\equiv x(\mod p)]\\ =\sum_{1\leq x<p}(\sum_{1\leq a<p,0\leq c<p-1}[a^c\equiv x(\mod p)])^2 \] 令$g$为$p$的原根,令$a=g^b$,$x=g^{x'}$有: \[ \sum_{1\leq x<p}(\sum_{1\leq a<p,0\leq c<p-1}[a^c\equiv x(\mod p)])^2\\ =\sum_{0\leq x'<p-1}(\sum_{0\leq b< p-1,0\leq c<p-1}[bc\equiv x'(\mod p-1)])^2\\ =\sum_{0\leq x<p-1}(\sum_{0\leq a,b<p-1}[ab\equiv x(\mod p-1)])^2\\ \] 考虑前面那个式子,如果我们令$x=x_0x_1,x_0\bot x_1$,$p-1=p_0p_1,p_0\bot p_1$,其中$0\leq x_0<p_0,0\leq x_1<p_1$,后面那个式子为$f(p-1,x)$,由于中国剩余定理,有$f(p-1,x)=f(p_0,x_0)f(p_1,x_1)$.

于是令$p-1=\prod_{i=1}^kp_i^{q_i}$上面的式子可以改为: \[ \prod_{i=1}^k(\sum_{0\leq x_i<p_i^{q_i}}(\sum_{0\leq a,b<p_i^{q_i}}[ab\equiv x_i(\mod p_i^{q_i})])^2) \] 我们只考虑其中一项,形如: \[ \sum_{0\leq x<p^{q}}(\sum_{0\leq a,b<p^q}[ab\equiv x(\mod p^{q})])^2 \] 我们不妨用$ap^{\alpha}$代替$a$,$bp^\beta$代替$b$,$xp^t$代替$x$,其中$a,b,x\bot p$那么有: \[ \sum_{0\leq x<p^{q-t}}(\sum_{0\leq a< p^{q-\alpha},0\leq b<p^{q-\beta}}[abp^{\alpha+\beta}\equiv xp^t(\mod p^{q})])^2 \] 则我们要做的即对四元组$(a,b,\alpha,\beta)$计数.由于$a,b,x\bot p$,我们有: \[ \alpha+\beta=t,\alpha,\beta\in\mathbb{N}\\ ab\equiv x\pmod {p^{q-t}},0\leq a<p^{q-\alpha},0\leq b<p^{q-\beta} \] 第一个式子对四元组的贡献显然是$t+1$,而第二个式子,由于$[1,p^{q-t})\in[1,p^{q-\alpha})$,所以我们可以先求出$1\leq a<p^{q-t}$的答案,然后乘以$p^{t-\alpha}$得到答案,$b$是类似的,于是: \[ ans=\sum_{1\leq x<p^{q-t}}((t+1)p^{t-\alpha}p^{t-\beta}\sum_{1\leq a,b< p^{q-t}}[ab\equiv x\pmod {p^{q-t}}])^2+(\sum_{1\leq a,b\leq p^q}[ab\equiv 0\pmod {p^{q}}])^2\\ =\sum_{1\leq x<p^{q-t}}((t+1)p^{t-\alpha}p^{t-\beta}\sum_{1\leq a,b< p^{q-t}}[ab\equiv x\pmod {p^{q-t}}])^2+q(p-1)p^{q-1}+p^q \] 后面,由于$a\bot p$,显然一个$a$唯一对应一个$b$.于是我们得到了答案为: \[ \sum_{1\leq x<p^{q-t}}((t+1)p^{t}\varphi(p^{q-t}))^2 \] 而后面的式子显然跟$x$无关,所以有: \[ \sum_{0< x<p^{q-t}}((t+1)p^{t}\varphi(p^{q-t}))^2\\ =\sum_{0\leq t< q}(\varphi(p^{q-t}))((t+1)p^{t}\varphi(p^{q-t}))^2\\ =\sum_{0\leq t<q}(t+1)^2p^{2t}(p-1)^3p^{3q-3t-3}\\ =\sum_{0\leq t<q}(t+1)^2(p-1)^3p^{3q-t-3} \] 其实到这一步,由于$\sum t$是$O(\log n)$级别的,这题已经可以做了.

莫比乌斯函数

莫比乌斯函数$\mu(x)$是一个满足$\sum_{d|n}\mu(n)=1$的函数,根据定义其显然是积性函数.根据定义可以求出它的封闭形式:

$\mu(m)=\begin{cases}0&\exist m_i\geq 2\\(-1)^k&\forall m_i\leq 1\end{cases},m=\prod_{i=1}^kp_i^{m_i}$.

莫比乌斯反演

见”反演.md”.

另外,值得一提的是,根据莫比乌斯反演,我们可以发现$\mu*id=\varphi$.

有公式:$\mu^2(x)=\sum_{i^2|x}\mu(i)$.原因很简单,我们设$x'$为$x$中所有的质因子的幂先除二下取整再乘二后变成的答案,显然$\mu^2(x)=\mu^2(x')$,我们有$\sum_{i|\sqrt {x'}}\mu(y)=[\sqrt {x'}=1],\sum_{i^2|x'}\mu(y)=[x'=1]$.

min25筛

如果我们考虑积性函数的值,理论上来说,设$S(n,k)$表示最小质因子大于等于$p_k$的所有$f$的和加上$f(1)$,其实我们自然有: \[ S(n,k)=\sum_{e\geq 0}f(p_k^e)S(\lfloor\frac{n}{p_k^e}\rfloor,k+1) \] 问题在于这么做需要枚举$[1,n]$中的全部质数,这是根本无法接受的.

我们考虑一些很大的质数,换言之,最小质因子大于$\sqrt n$的数在$[1,n]$中只有可能是质数本身.

因此你会发现,这个过程只需要把质数单独拿出来做,复杂度就可以得到相当的飞跃.

考虑: \[ \sum_{i=1}^nf(i)=\sum_{p\in prime}f(p)+\sum_{p\notin prime\and p\ne 1}f(p)+f(1) \]

令$g(N,i)=\sum_{j=1}^N[j\in prime \or Min_j>p_i]F(j)\\$,其中$Min_j$表示$j$最小的质因数,$p_i$表示第$i$个质数.

注意到$g(N,i)$实际上就是$N$以内的数在第$i$轮埃氏筛后剩余的数的$F$的和.

$F(i)$表示若干完全积性函数之和且当$p\in prime$ 时,$F(p)=f(p)$,下文为了方便书写,直接认为$F$是完全积性函数.

而$g(N,\sqrt N)$实际上就是$N$以内的质数的$F$之和,那么有: \[ g(n,0)=\sum_{i=2}^nF(i)\\ g(i,j)=g(i,j-1)-F(p_j)(\ g(\lfloor\frac{i}{p_j}\rfloor,j-1)-\sum_{2\leq p\leq p_{j-1},p\in prime}F(p)\ )\\ \] ps1:

第$j$个质数会比第$j-1$个多筛若干个数,即最小质因数是$p_j$的数.这些数形如$\{p_j,2p_j,3p_j...\}$,同时除以$p_j$得到$\{1,2,3...\}$.

我们要的就是其中最小质因数大于等于$p_j$的数,也就是最小质因数大于$p_{j-1}$的数,因而就是$g(\lfloor\frac{i}{p_j}\rfloor,j-1)$.

但还有一些质数会被重复计算,我们把他删掉就可以了.

考虑到$g$后面的维度最多走到$\sqrt n$,所以我们所枚举的最小质因子一定小于等于$\sqrt n$,所以一定有$p_{j-1}<\lfloor\frac{i}{p_j}\rfloor$,所以直接删去一定不会多删.

ps2:

注意到以下事实:$\lfloor\frac{\lfloor\frac{a}{b}\rfloor}{c}\rfloor=\lfloor\frac{a}{bc}\rfloor\\$.

因而,如果我们有以下代码:

void solve(int n){
    if(f[n])return f[n];
    else f[n]=......;
    for(int i=1;i<=n;++i){
        solve(n/i);
    }
}
int main(){
    ...
    solve(n);
    ...
}

该代码复杂度为$O(\sqrt n)$.原因在于,根据整数分块,$\lfloor\frac{n}{i}\rfloor$有$\sqrt n$种取值.

而如果递归下去,继续枚举$j$,并往下递归到$\lfloor\frac{\lfloor\frac{n}{i}\rfloor}{j}\rfloor$,那他就相当于枚举$k=ij$,并递归到$\lfloor\frac{n}{k}\rfloor$,因而复杂度得到保证.

由此可知,求$g$的复杂度为$O(\sqrt n\times \sqrt {\sqrt n})=O(n^{\frac3 4})$.

令$S(n,m)$表示前$n$个数中,最小质因数大于等于$p_m$的数的$f$之和,可知: \[ S(n,m)=g(n,+\infty)-\sum_{k=1}^{m-1}f(p_k)+\sum_{k\geq m,e\geq 1,p_k^{e+1}\leq n}f(p_k^e)S(\lfloor\frac{n}{p_k^e}\rfloor,k+1)+\sum_{k\geq m,e=2,p_k^e\leq n}f(p_k^e)\\ =g(n,+\infty)-\sum_{k=1}^{m-1}f(p_k)+\sum_{k\geq m,e\geq 1,p_k^{e+1}\leq n}[f(p_k^e) S(\lfloor\frac{n}{p_k^e}\rfloor,k+1)+f(p_k^{e+1})]\\ \] ps1:

前半段求出质数部分的和,后半段开始枚举最小质因子.

由于$p_k$是当前数的最小质因子,$e$是他的幂.则这个数其他的质因子应该均大于$p_k$,因而大于等于$p_{k+1}$.

注意到由于$S$中不包含$1$,所以应特殊处理只含有$p_k$一个质因子的情况.

又注意到,如果$p_k^e< n<p_k^{e+1}$,那么此时$\lfloor\frac{n}{p_k^e}\rfloor$一定小于$p_k$,则不可能拥有比$p_k$更大的质因子.

该形式与上面一致,因而复杂度同样为$O(n^{\frac 3 4})$.我们最终要求的答案即$S(n,1)+f(1)$.

一些后记:

事实上,复杂度的计算只是上限,实际上应该约为$O(\frac{n^{\frac3 4}}{\log_2 n})$.
如果使用map会导致复杂度较差,考虑如下事实: (1).$\forall 1\leq x\leq n$,则要么$x\leq \sqrt n$,要么$\lfloor\frac{n}{x}\rfloor\leq \sqrt n\\$. (2).$\forall a$形如$\lfloor\frac{n}{x}\rfloor$,则$\lfloor\frac{n}{a}\rfloor$应为$x_{max}$,互不相同. 因而可以分别特判,从而做到比map或离散化都优秀的复杂度.
我们在代码中所求出的$w$是倒序的,而我们转移的过程也是倒序的,因而枚举的时候可以直接正序枚举.
考虑做的时候由于进行了滚动数组,因而继承操作可以直接使用,为了方便可以直接判掉可以直接继承的情况.
求$S$的过程可以使用递归,因为我们只关心一个$S$的量.

Example1([uoj188]Sanrd)

注意到这题显然可以写埃筛的暴力.考虑使用类似min15筛的方式,定义$f(n)$为$n$的次大质因子(若$n=1\or n\in prime$则$f(n)=0$),$S(n,k)=\sum_{i=1}^n[Min_i\geq p_k]f(i)$.不难发现我们要求的就是$S(n,1)$,而显然$S(n,\sqrt n)=0$.

注意到: \[ S(n,m)=\sum_{i\geq m,e\geq 1,p_i^{e+1}\leq n}S(\lfloor\frac{n}{p_i^e}\rfloor,i+1)+p_i\sum_{i=p_i+1}^{\lfloor\frac{n}{p_i^e}\rfloor}[i\in prime] \] 区间素数个数可以拿min25筛的前半部分做.

杜教筛

令$F(n)=\sum_{i=1}^nf(i)\\$,我们考虑构造两个函数$g$和$s$.使得$f*g=s$.

令$G(n)=\sum_{i=1}^ng(i),S(n)=\sum_{i=1}^ns(i)\\$.若$G(i)$和$S(i)$都很方便求,$g(1)=1$,我们就可以求出$F(n)$. \[ f*g=s\\ \sum_{j|i}f(j)g(\frac i j)=s(i)\\ \] 由于$g(1)=1$,我们有$f(i)=s(i)-\sum_{j|i,j\ne i}f(j)g(\frac i j)\\$.

那么: \[ F(n)=\sum_{i=1}^nf(i)\\=\sum_{i=1}^n(s(i)-\sum_{j|i,j\ne i}f(j)g(\frac i j))\\ =S(n)-\sum_{j=1}^n\sum_{k=2}^{\lfloor\frac n j\rfloor}g(k)f(j)\\=S(n)-\sum_{k=2}^ng(k)\sum_{j=1}^{\lfloor\frac n k\rfloor}f(j)\\ =S(n)-\sum_{k=2}^ng(k)F(\lfloor\frac n k\rfloor)\\ \] 复杂度证明和min25筛是一样的,不同点在于我们可以预处理$n^{\frac 2 3}$以内的$F$,这样复杂度可以降到$O(n^{\frac 2 3})$.

#####Example1

求$\sum_{i=1}^N\mu(i)\\$.

由于$\mu*I=\epsilon$,于是考虑$g=I$.

#####Example2

求$\sum_{i=1}^N\varphi(i)\\$.

由于$\varphi*I=id$,于是考虑$g=I$.

#####Example3

求$\sum_{i=1}^N{\varphi(i)\times i}\\$ 由于$\sum^N_{i=1}(f*g)(i)=\sum_{d|N}{f(i)\times g(\cfrac n d)}=\sum_{d|N}{\varphi(d)\times d\times g(\cfrac n d)}\\$ 由于中间过程中乘出来的$d$很难处理,需要消掉它,于是考虑$g=id$.

#####Example4

$\sum_{i=1}^N{\varphi(i)\times i^2}\\$. 由Example3,于是考虑$g=id^2$.

Powerful Number筛

定义Powerful Number为满足所有质因子的指数都$>1$的数,不难证明这样的数在$[1,n]$中最多只有$O(\sqrt n)$个(使用积分).同时对于质因子的幂分奇偶讨论:奇数分成一个$3$加上一个偶数,那么不难证明这个数一定有:$a^2b^3$的形式.找到这些数字可以直接dfs搜指数.

现在我们要求积性函数$f(n)$的前缀和.假设$f=h*g$,其中$h(1)=1,g(p)=f(p),\forall p\in prime$且$g(n)$的前缀和容易计算.

接下来我们证明:$h(n)\ne0\Rightarrow n\ is\ Powerful\ Number$.

$\forall p\in prime$,$f(p)=g(1)h(p)+g(p)h(1)=h(p)+g(p)$,于是$h(p)=0$.根据积性函数的性质有$\forall x\notin \text{PN},h(x)=0$.

注意到: \[ F(n)=\sum_{i=1}^nf(i)\\ =\sum_{i=1}^n\sum_{j|i}h(j)g(\frac{i}j)\\ =\sum_{j=1}^nh(j)G(\lfloor\frac{n}{j}\rfloor) \] 于是可以快速求,复杂度$O(\sqrt n)$.

Example1([SP20174]DIVCNT3)

首先我们需要构造$g(p)=f(p),p\in prime$.注意到$f(p)=d(p^3)=4$,我们构造$g(p)=(d*d)(p)$.这样问题在于求$G(n)$.我们有: \[ G(n)=\sum_{i=1}^n(d*d)(i)\\ =\sum_{ij\leq n}d(i)d(j)\\ =\sum_{i=1}^nd(i)D(\lfloor\frac{n}{i}\rfloor) \] 而$D(n)=\sum_{i=1}^n\lfloor\frac{n}{i}\rfloor$,自然可以做.复杂度算一算是$O(n^{\frac{2}{3}})$.

感觉Powerful Number筛的关键在于构造.

整值函数

定义

若$x\in\mathbb{R}$,则:

$\lfloor x\rfloor=$小于等于x的最大的整数.

$\lceil x\rceil=$大于等于x的最小的整数.

我们有时称$\lfloor x\rfloor$为$x$的整数部分,并定义$x-\lfloor x\rfloor$为分数部分,有时记作$\{x\}$.

我们定义$x\mod y=x-y\lfloor\cfrac{x}{y}\rfloor$,$x\ mumble\ y=y\lceil\cfrac{x}{y}\rceil-x$,其中$x,y\in \mathbb{N_+}$.

当然,我们也可以使用上述定义将$mod$和$mumble$的定义扩展到实数域,不过$y=0$的时候需要特殊处理.

整值函数的基本性值

若$x\in \mathbb{R},n\in \mathbb{Z}$,则有:

$\lfloor x\rfloor=x \Leftrightarrow \lceil x\rceil=x\Leftrightarrow x\in \mathbb{Z}$.
$\lceil x\rceil-\lfloor x\rfloor=[x\notin \mathbb{Z}]$.
$x-1<\lfloor x\rfloor\leq x\leq \lceil x\rceil<x+1$.
$\lfloor-x\rfloor=-\lceil x\rceil,\lceil -x\rceil=-\lfloor x\rfloor$.
$\lfloor x \rfloor=n\Leftrightarrow n\leq x<n+1 \Leftrightarrow x-1<n\leq x$.
$\lceil x\rceil =n\Leftrightarrow n-1<x\leq n\Leftrightarrow x\leq n<x+1$.
$x<n\Leftrightarrow \lfloor x\rfloor<n$.
$x\leq n\Leftrightarrow \lceil x\rceil\leq n$.
$x>n\Leftrightarrow \lceil x\rceil>n$.
$x\geq n\Leftrightarrow \lfloor x\rfloor\geq n$.
$\lfloor x+n\rfloor=\lfloor x\rfloor+n$.
$\lceil x+n\rceil=\lceil x\rceil+n$.
$\lfloor nx\rfloor=n\lfloor x\rfloor\Leftrightarrow n=0\or x-\lfloor x\rfloor< \cfrac{1}n$.
$\lceil nx\rceil=n\lceil x\rceil\Leftrightarrow n=0\or x-\lceil x\rceil< \cfrac{1}n$.
$\lceil\cfrac{n}{m}\rceil=\lfloor\cfrac{n-1}{m}\rfloor+1,m\in\mathbb{N_+}$.
$m\lceil x\rceil-\lceil m(\lceil x\rceil-x)\rceil=\lfloor mx\rfloor$.
$(x\mod ny)\mod y=x\mod y,n\in\mathbb{N_+}$.
分配律:$c(x\mod y)=(cx)\mod (cy)$.

整值函数的应用

一类函数与整值函数

设$f(x)$是一个有以下性质且在一个实数区间连续的单调递增函数:

$f(x)\in \mathbb{Z}\Rightarrow x\in \mathbb{Z}$.

那么,只要$f(x),f(\lfloor x\rfloor),f(\lceil x\rceil)$都有定义,我们有:

$\lfloor f(x)\rfloor=\lfloor f(\lfloor x\rfloor) \rfloor$和$\lceil f(x)\rceil=\lceil f(\lceil x\rceil) \rceil$.

由于底和顶是类似的,我们考虑先对顶进行证明,这样也可以类似证明底:

若$x=\lceil x\rceil$,显然得证;

不然,有$x<\lceil x\rceil$,那么有$f(x)<f(\lceil x\rceil)$,也就有$\lceil f(x)\rceil\leq \lceil f(\lceil x\rceil) \rceil$.

考虑反证法,不妨令$\lceil f(x)\rceil<\lceil f(\lceil x\rceil) \rceil$.则一定存在一个整数$y$使得$\lceil f(x)\rceil=y<\lceil f(\lceil x\rceil) \rceil$,此时必有$x\leq y<\lceil x\rceil$.由于$f$的性值,显然有$y$是整数,但根据整值函数的性值,不可能存在这样一个整数$y$满足$x\leq y<\lceil x\rceil$,因此得证.

另外,我们考虑函数$f(x)=\cfrac{x+m}{n}$,显然这是一个满足条件的函数,因此显然满足上述的条件.再考虑$m=0$的特殊情况:$\lfloor \cfrac{\lfloor\cfrac{x}{n}\rfloor}{m}\rfloor=\lfloor\cfrac{x}{nm}\rfloor$.

而单调递减函数可以取相反数转化为单调递增函数.

迪利克雷抽屉原理

$n$个物体放进$m$个盒子里,那么必定有一个盒子中放入了大于等于$\lceil\cfrac n m\rceil$个物品,有一个盒子放入了小于等于$\lfloor\cfrac n m\rfloor$个物体.

Example1

求证:每个由$n^2+1$个不同实数构成的序列都包含一个长为$n+1$的严格递增子序列或严格递减子序列.

设$a_i$为第$i$个实数,$c_i$为以这个数为开头的最长的递增子序列,$d_i$表示以这个数为开头的最长的递减子序列.考虑反证法,如果不成立,那么$\forall 1\leq i\leq n^2+1$,$1\leq c_i\leq n\and 1\leq d_i\leq n$.那么一共有$n^2$种不同的有序对.

根据抽屉原理,一共有$n^2+1$个有序对,所以一定有两个有序对相等.由于这些数字两两不同,所以一定可以把其中一个数字加到另一个数字的递增或递减子序列的后面,这样那个数字的$c_i$或者$d_i$就要$+1$,与我们的假设不符,因此该定理成立.

Example2

求证:若任意两个人间只有两种关系:朋友或敌人.那么对于六个人而言,一定有三个人两两都是朋友或者两两都是敌人.

令$A$是这六个人中其中一个,根据抽屉原理,一定有大于等于$3$个人都是$A$的敌人或者都是$A$的朋友,不妨假设这三个人都是$A$的朋友.

如果这三个人中有两个人是朋友,那么它们和A就一起构成了一组人.不然,他们三个人就构成了一组人.

计算区间内整数个数

整值函数的另一个应用是计算区间内整数个数:

考虑基本性值$7,8,9,10$,不难发现:

$[\alpha,\beta]$包含$\lfloor\beta\rfloor-\lceil\alpha\rceil+1$个整数.
$(\alpha,\beta)$包含$\lceil\beta\rceil-\lfloor\alpha\rfloor-1$个整数.
$(\alpha,\beta]$包含$\lfloor\beta\rfloor-\lfloor\alpha\rfloor$个整数.
$[\alpha,\beta)$包含$\lceil\beta\rceil-\lceil\alpha\rceil$个整数.

谱

我们定义一个实数$\alpha$的谱是以下集合:

$Spec(\alpha)=\{\lfloor\alpha\rfloor,\lfloor2\alpha\rfloor,\lfloor3\alpha\rfloor...\}$.

不难发现,只要$\alpha\ne\beta$,则$Spec(\alpha)\ne Spec(\beta)$.

Example

求证:$Spec(\sqrt2)\cup Spec(2+\sqrt2)=\mathbb{N_+}$且$Spec(\sqrt2)\cap Spec(2+\sqrt2)=\phi$,即这两个集合构成了正整数集的一个划分.

我们考虑这样一个事实:对于任意正整数$n$,如果我们能求出来$Spec(\sqrt2)$中有$a$个元素$\leq n$,$Spec(2+\sqrt2)$中有$b$个元素$\leq n$,并且$a+b=n$,则结论显然成立.

不妨令函数$N(\alpha,n)$表示$Spec(\alpha)$中有多少个元素$\leq n$,其中$\alpha$是正数,我们有: \[ N(\alpha,n)=\sum_{k\in\mathbb{N_+}}[\lfloor k\alpha\rfloor\leq n]\\ =\sum_{k\in\mathbb{N_+}}[\lfloor k\alpha\rfloor< n+1]\\ =\sum_{k\in\mathbb{N_+}}[k\alpha< n+1]\\ =\sum_k[0<k<(n+1)/\alpha]\\ =\lceil(n+1)/\alpha\rceil-1 \] 则我们要证明的就是: \[ \lceil\cfrac{n+1}{\sqrt2}\rceil-1+\lceil\cfrac{n+1}{2+\sqrt2}\rceil-1=n\\ \lfloor\cfrac{n+1}{\sqrt2}\rfloor+\lfloor\cfrac{n+1}{2+\sqrt2}\rfloor=n\\ \cfrac{n+1}{\sqrt2}-\{\cfrac{n+1}{\sqrt2}\}+\cfrac{n+1}{2+\sqrt2}-\{\cfrac{n+1}{2+\sqrt2}\}=n \] 而由于我们有恒等式:$\cfrac1{\sqrt2}+\cfrac{1}{2+\sqrt2}=1$,且两个相加为整数的数的分数部分相加显然为$1$,原式得证.

事实上,如果两个集合$Spec(\alpha)$和$Spac(\beta)$构成正整数集一个划分,可以同上证明$\cfrac1\alpha+\cfrac1\beta=1$且$\alpha$和$\beta$都是无理数.

整值函数的递归式

得到递归式的封闭形式的确很有用,它可以让我们在很快的时间内求出答案,但大部分时候是很麻烦的.

而如果我们对时间的要求没有那么紧,我们不妨考虑一种较慢但更容易的方法:

Example

约瑟夫问题,但是每隔两个人处死一个人,求最后存活者的编号.

我们不妨这样考虑:我们每略过两个人,就将他们重新编号.

例如,我们杀掉了三号,就将一号和二号重新编号为$n+1$号和$n+2$号,杀掉了六号,就将四号和五号重新编号为$n+3$号和$n+4$号,这样,我们在做游戏的时候,场上人员的编号一定是连续的.

我们把最后存活者改为最后死亡者,这样它的最后编号就是$3n$.

并且不难发现,第$k$个死亡的人的最后编号就是$3k$.

我们考虑已知新编号如何求旧编号,设新编号为$N$:

如果$N\leq n$,则$N$是初始编号,反之,我们考虑在编号$N$的时候被杀死的人的编号.

假设现在进行完了$k+1$轮,令$N=n+2k+w$,其中$w\in\{1,2\}$,则编号$N$的时候被杀死的即是$3(k+1)$,那么$N$之前的编号就是$3k+w=N-(n-k)=N-n+k$.

而$k=\lfloor\cfrac {(N-n-1)}{2}\rfloor$,我们可以不断进行迭代.

如果我们令$D=3n+1-N$,换句话说即改变编号的顺序,我们可以有以下的赋值操作:

$3n+1-D'=3n+1-D-n+\lfloor\cfrac {(3n+1-D-n-1)}{2}\rfloor$.

化简这个式子,我们有:$D'=D+n-\lfloor\cfrac {(2n-D)}{2}\rfloor=D+\lceil\cfrac{D}{2}\rceil=\lceil\cfrac{3D}2\rceil$.

事实上,我们可以证明:如果我们每隔$q$个人就杀掉一个人的话,那么$D'=\lceil\cfrac{(q+1)D}{q}\rceil$,一直迭代到$D'>qn$时.

而最后的答案就是$(q+1)n+1-D$.

整值函数的恒等式

考虑公式$\lceil\cfrac{n-k+1}{m}\rceil$,不难发现它在$1\leq k\leq n\mod m$时的值为$\lceil\cfrac{n}{m}\rceil$,而在$n\mod m<k\leq m$的值为$\lfloor\cfrac n m\rfloor$.

那么我们可以得到以下恒等式:

$n=\sum_{k=1}^m\lceil\cfrac{n-k+1}{m}\rceil$.

类似地,有:

$n=\sum_{k=1}^m\lfloor\cfrac{n+k-1}{m}\rfloor$.

用$\lfloor mx\rfloor$替换上面的$n$有$\lfloor mx\rfloor=\sum_{k=1}^m\lfloor x+\cfrac{k-1}{m}\rfloor$.

同样的,有$\lceil mx\rceil=\sum_{k=1}^m\lceil x-\cfrac{k-1}{m}\rceil$.

整值函数的和式

通常情况下,处理含整值函数的和式时,通过引入新变量进行代替以及通过转化为区间进行化简.

如果遇到难以处理的情况,我们不妨考虑直接处理其中一段的和,使得剩下部分求和更为简单.

处理整值函数的另一个方法是:考虑将整值函数内的东西移出,并且让里面的东西形如等差序列,这样我们就可以尝试使用恒等式来化简.

Example1

求$\sum_{k=0}^{n-1}\lfloor\sqrt k\rfloor$.

我们有: \[ \sum_{k=0}^{n-1}\lfloor\sqrt k\rfloor=\sum_{0\leq k,m}[k<n][m=\lfloor\sqrt k\rfloor]m\\ =\sum_{0\leq k,m}[k<n][m^2\leq k<(m+1)^2]m\\ =\sum_{0\leq k,m}m[m^2\leq k<n<(m+1)^2]+\sum_{0\leq k,m}m[m^2\leq k<(m+1)^2\leq n] \] 考虑$n=a^2$的特殊情况,则前面那一项显然是$0$,那么: \[ ans=\sum_{0\leq k,m}m[m^2\leq k<(m+1)^2\leq n]\\ =\sum_{0\leq m}m(2m+1)[m<a]\\ =\sum_{m=0}^{a-1}(2m^2+m)\\ =\cfrac{(a-1)a(2a-1)}{3}+\cfrac{a(a-1)}{2}\\ =\cfrac{(4a+1)a(a-1)}{6} \] 而如果$n\ne a^2$,我们令$a=\lfloor\sqrt n\rfloor$,而当$k\in [a^2,n)$的部分的贡献显然是$a(n-a^2)$.

于是最后的结果就是:$\cfrac{(4a+1)a(a-1)}{6}+a(n-a^2),a=\lfloor\sqrt n\rfloor$.

另一个做法是,我们考虑增加枚举量,有: \[ \sum_{k=0}^{n-1}\lfloor\sqrt k\rfloor=\sum_{j,k}[1\leq j\leq \sqrt k][0\leq k<a^2]\\ =\sum_{1\leq j<a}\sum_{k}[j^2\leq k<a^2]\\ =\sum_{1\leq j<a}a^2-j^2=a^3-\cfrac{a(2a+1)(a+1)}{6} \]

Example2(类欧几里得算法)

求$\sum_{k=0}^{m-1}\lfloor\cfrac{nk+x}{m}\rfloor,m\in\mathbb{N_+},n\in \mathbb{Z}$.

由于$kn-(kn\mod m)=m\lfloor\cfrac{kn}{m}\rfloor$,我们有:

\[ \lfloor\cfrac{x+kn}{m}\rfloor=\lfloor\cfrac{x+(kn\mod m)}{m}\rfloor+\cfrac{kn}{m}-\cfrac{kn\mod m}{m} \] 这样,我们将整个式子的求和分为了三部分,第二项显然是等差数列求和,而如果我们令$g=\gcd(n,m)$,不难发现第三项的分子是一个等差数列$0,g,2g,...m-g$重复了$g$次,而且正因为这,第一项里面的数也就自然组成了等差数列,由于我们有恒等式,那么这一项也就自然可以计算了.

分别求和后加起来,得到答案为$g\lfloor\cfrac{x}{g}\rfloor+\cfrac{(m-1)n}{2}+\cfrac{g-m}{2}$.

另外,对这个式子进行化简,我们可以得到:$g\lfloor\cfrac{x}{g}\rfloor+\cfrac{(m-1)(n-1)}{2}+\cfrac{g-1}2$,而这个式子关于$n$和$m$是对称的.

也就是说:$\sum_{k=0}^{m-1}\lfloor\cfrac{nk+x}{m}\rfloor=\sum_{k=0}^{n-1}\lfloor\cfrac{mk+x}{n}\rfloor,m,n\in\mathbb{N_+}$.

另外,如果要求$\sum^n_{i=0}\lfloor\cfrac{ai+b}{c}\rfloor$,我们也有一种$O(\log n)$的做法(类欧几里得算法):

若$c\leq a$,原式化为$\sum^n_{i=0}{(i\times\lfloor\frac{a}{c}\rfloor+\lfloor\cfrac{(a\mod c)i+b}{c}\rfloor)}$.

若$c\leq b$,原式化为$\sum^n_{i=0}{\lfloor\cfrac{b}{c}\rfloor+\lfloor\cfrac{ai+(b\mod c)}{c}\rfloor}$.

考虑$a,b<c$的情况,设$m=\lfloor\cfrac{an+b}{c}\rfloor$,原式化为 \[ \sum^n_{i=0}\sum^m_{j=1}[j\leq \lfloor\cfrac{ai+b}{c}\rfloor]\\=\sum^n_{i=0}\sum^m_{j=1}[cj\leq ai+b]\\=nm-\sum^n_{i=0}\sum^m_{j=1}[ai\leq cj-b-1]\\=nm-\sum^m_{i=1}\lfloor\cfrac{ci-b-1}{a}\rfloor \]

#####Example3

求$\sum_{n=1}^{1000}[\lfloor\sqrt[3]n\rfloor|n]$. \[ ans=\sum_{n,k}[k=\lfloor\sqrt[3]n\rfloor][k|n][1\leq n\leq 1000]\\ =\sum_{k,m,n}[k^3\leq n<(k+1)^3][n=km][1\leq n\leq 1000]\\ =1+\sum_{k,m}[k^3\leq km<(k+1)^3][1\leq k< 10]\\ =1+\sum_{k,m}[k^2\leq m<\frac{(k+1)^3}k][1\leq k<10]\\ =1+\sum_{k=1}^9(\lceil k^2+3k+3+\frac1 k\rceil-\lceil k^2\rceil)\\ =1+\sum_{k=1}^9(3k+4)=172 \] 上述推理过程将$n=1000$的情况特殊讨论了一下,不难发现,如果我们要求的式子是$\sum_{n=1}^{N}[\lfloor\sqrt[3]n\rfloor|n]$,也仍然可以使用将$[K^3,N],K=\lfloor\sqrt[3]N\rfloor$中的数特殊处理的方式做掉,因为这些数的三次根下取整一定是$K$,式子就不难化简了.

Example4([uoj42]Sum)

这题的重点在于将幂通过$-1$的性质拿下来.

我们有$(-1)^a=1-2(a\mod 2)=1-2(a-2\lfloor\frac{a}{2}\rfloor)$.

于是我们有: \[ \sum_{d=1}^n(-1)^{\lfloor d\sqrt r\rfloor}\\=n-2\sum_{d=1}^n\lfloor d\sqrt r\rfloor+4\sum_{d=1}^n\lfloor\frac{\lfloor d\sqrt r\rfloor}{2}\rfloor\\ \] 令$f(x)=\frac{x}2$,根据整值函数的性质,不难发现$\lfloor\frac{\lfloor d\sqrt r\rfloor}{2}\rfloor=\lfloor\frac{d\sqrt r}{2}\rfloor$.

于是我们有: \[ ans=n-2\sum_{d=1}^n\lfloor d\sqrt r\rfloor+4\sum_{d=1}^n\lfloor\frac{d\sqrt r}{2}\rfloor\\ \] 记$t=\sqrt r$,我们所要解决的问题是$\sum_{d=1}^n\lfloor d\frac{Pt+R}{Q}\rfloor$.如果$\frac{Pt+R}{Q}\geq 1$,我们可以把整数部分取出来单独算.于是接下来我们只讨论$0\leq \frac{Pt+R}{Q}<1$的情况.相当于求一条斜率小于$1$的直线下方的整点个数.我们可以反转坐标系,这样就变成了斜率大于$1$的直线,继续做上面的操作.

这个问题引出万能欧几里得算法.

Example5([loj6440]万能欧几里得算法)

解决形如$\sum_{x=1}^{L}A^xB^{\lfloor\frac{Px+R}{Q}\rfloor}$的问题,其中$A$和$B$都是$n\times n$的矩阵.默认$P,Q,R\geq 0$.

我们将问题抽象为下面的模型:

首先将坐标系中所有经过整数点的与坐标轴平行的直线全都标记出来.

考虑将问题转化为:有一条$y=\frac{Px+R}{Q}$的直线,我们从$(0,\frac{R}{Q})$(不包含这个点)处开始沿直线向右走.每遇到一条横线,就进行$U_w$操作;每遇到一条竖线,就进行$R_w$操作.如果遇到了整数格点,就先进行$U_w$操作,再进行$R_w$操作.

例如上面那个例子就是:现在有一个矩阵二元组$(X,Y)$,初始为$(A,B^{\lfloor\frac{R}{Q}\rfloor})$,$R_w$操作是:$(X,Y)\rightarrow (AX,Y+X)$,$U_w$操作是:$(X,Y)\rightarrow(XB,Y)$.一直走到$x=L$的点为止,最后矩阵$Y$就是答案.不过这个形式不好写成矩阵,我们可以记录$(A^a,B^b,Y)$.这样最后就可以带入操作,不难发现这个操作是个环.

操作要满足可合并性,也就是我可以将$U_wR_w$变成一个操作进行.

接下来我们分情况讨论一下:

当$P\geq Q$时,注意到$y=\frac{Px+R}{Q}=\lfloor\frac{P}{Q}\rfloor x+\frac{(P\mod Q)x+R}{Q}$,此时任意一个$R_w$操作前必然有至少$\lfloor\frac{P}{Q}\rfloor$个$U_w$,我们令$R_w'=U_w^{\lfloor\frac{P}{Q}\rfloor}R_w$,不难发现:$solve(P,Q,R,L,U_w,R_w)=solve(P\mod Q,Q,R,L,U_w,R_w')$.

当$P<Q\and P\ne 0$时,我们想要让$P$与$Q$互换,假设第$a$个$R_w$在第$b$个$U_w$之前,考虑这个$R_w$前会有$\lfloor\frac{Pa+R}{Q}\rfloor-\lfloor\frac{R}{Q}\rfloor$个$U_w$,而对于后者,变换坐标系得到$x=\frac{yQ-R}{P}$,由于遇到整点时,先$U_w$再进行$R_w$,也就是说,第$b$个$U_w$前会有$\lfloor\frac{Qb-R-1}{P}\rfloor$个$R_w$(这个并没有忽略初始位置).我们考虑如何让这个数和上面的$\lfloor\frac{Pa+R}{Q}\rfloor$的差分写成一样的形式.注意到$b=1$需要特殊处理!

显然操作序列一共有$cntU=\lfloor\frac{PL+R}{Q}\rfloor-\lfloor\frac{R}{Q}\rfloor$,将二者对应一下,这里的答案就是$solve(Q,P,(Q-R-1)\bmod P,cntU-1,R_w,U_w)$.

然后是开头部分,开头部分一共有$\lfloor\frac{Q-R-1}{P}\rfloor$个$R_w$和一个$U_w$.

但是注意到末尾部分同样是不规整的,注意到末尾一共有$L-\lfloor\frac{QcntU-R-1}{P}\rfloor$个$R_w$,拼到末尾即可.

最后$P=0$的时候直接返回$R_w^{L}$即可.

假设合并的复杂度是$c$,注意到每层的复杂度是$O(c\log(\frac{Q}{P}))=O(c(\log Q-\log P))$,但是每两层会抵消,因此复杂度$O(C\log(P+Q))$.