数论相关 · LWLAymh的备忘录

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

整除性及相关

如果且是一个整数,我们就说整除,记作.

能同时整除两个数和的数称为和的公因子,所有公因子中最大的那个称为最大公因子,记作.而最小的能同时被和整除的非零数被称为他们的最小公倍数,记作.不难发现.

欧几里得算法

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

且.

考虑证明,首先,,和的公因子一定是和的公因子,这是显然的.因此,和的公因子一定是和的公因子,而反之亦然.

另外有如下性质:

以及.
若,则.
如果,则.

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

不妨假设,当时显然成立.

当时:

假设,考虑.

取,则:

由于,所以显然,于是:

自然得证.

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

如果,显然得证.不然,不妨设注意到:

自然得证.

一些性质

令.

另外,有一个很著名的性质:对于数字,找到最小的正整数满足,.

首先令,我们自然有,也就相当于,由于,所以左边的可以用逆元消掉,显然最小正整数解为.

Example1([CF1656H]Equal LCM Subsets)

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

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

显然合法的条件等价于(当然这个还要反过来再写一遍,两个式子一起才是充要条件,这里为了方便只写一个),这个条件等价于.后者是方便做的.

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

基于值域预处理的快速 GCD

存在一种预处理,求任意两个小于等于的数的的方法:

引理:

对于任意整数,存在一种划分方式,,,三个数要么是质数,要么.

证明:

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

否则,使用数学归纳,我们考虑的最小质因子为,设,不妨设.

如果,显然成立.

不然有,而,那么,.

现在我们想要证明不存在,,.

如果存在,我们有:

与我们前面的结论不符合.

因而该引理成立,并且给出了预处理所有数的方法.

接下来，设,考虑使用的时间求出每个小于等于的数对的,如果我们要求,设,显然.

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

否则,因为,因而可以直接查表.

裴蜀定理

,则满足,当且仅当.

证明如下:

若或,显然成立.

不然,设集合中的最小正元素,该集合中显然一定有正元素.

考虑取该集合中另一个正整数,注意到,所以,如果,那么,与假设不符.所以这个集合里的所有数一定都是的倍数.

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

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

如果,可以取.

反之,显然其中有正有负(因为可以取),我们设取.,不妨设,那么,由于,所以,所以,是的倍数,且显然唯一.

扩展欧几里得算法

考虑求方程的一组解.

首先,如果,那这组解显然就是.

反之,我们令,考虑求方程的一组解.

接下来呢,考虑带入,则我们求出来的即方程的一组解.不难发现这也就是方程的一组解,所以原本的方程的解也就是.

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

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

题意:的格子图,只能往下往右走,走到边界会循环,问从开始走遍历走一个哈密顿回路的方案数.

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

由此我们发现,每条副对角线(取膜意义下)的状态必然相同,而取膜意义下的副对角线有多少条呢?不难注意到是条.也就是说,我们只需要确定这条对角线的值,就可以确定整个矩阵的答案.假设表示向右走,表示向下走,表示第条副对角线的状态,最后的操作序列自然是.

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

我们不妨假设序列中有个,个,那会产生这种情况当且仅当,.注意到这等价于寻找最小的,判断其是否小于,于是条件等价于自然有,枚举并判断即可.

素数及相关

定义

可以利用裴蜀定理证明素数的定义等价于.

考虑先用最基础的定义得到这个命题,考虑,则有解,则,右边都是的倍数,所以.

这个命题反推的话,考虑设,则且,不符.

Example1(《具体数学》4.22)

证明:在进制下,若的的个数不是质数则其一定不是质数..

设的个数为,则.

如果,不妨设则.

则

显然不是质数.

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

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

证明:

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

则对于,如果它不满足条件,一定存在两种分解方式.

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

不失一般性,设.则,显然,所以,设,但这是不可能的,因为,根据归纳假设,它只有一种分解方式,这种方式中显然不可能存在.

那么根据上述证明,我们可以将一个数表示为以下形式:.

另外不难证明的一点是,假设,那么最小质因子一定不大于.

Example1([CF986F]Oppa Funcan Style Remastered)

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

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

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

如果有三个质因子,此时最小质因子的大小就不大于,做同余最短路即可.

素数的个数

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

假设素数有有限个,分别为,则无法被其中任何素数整除,则假设不成立.

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

令表示小于等于的素数个数,有.

有切比雪夫定理(又称贝特朗假设):若.

又有狄利克雷定理:若中包含了无穷个素数.

(顺便一提,当或者,的时候是好证明的,由于素数要么形如要么形如,或者要么形如要么形如,只需要类似证明素数无限那样乘一乘)

同时,我们还有以下结论:.

证明如下:

Example1(《具体数学》4.20)

证明:存在一个常数满足都是质数.

如此构造数列:设,且为满足的最小质数.

通过构造不难发现:.

根据整值函数的性质,我们有.考虑反向数学归纳,考虑当时构造满足题目条件,那么,自然也满足条件.所以如果设为不断对迭代求做次后的答案,只需构造即可.

Example2

求证:

左推右是简单的.接下来考虑右推左.

考虑狄利克雷定理,数列.不妨反证,假设,不妨设,,也就是,注意到,此时必有,而无限,的素因子有限,这就导出了矛盾.

欧几里得数

定义欧几里得数:.不难发现.

费马数

定义费马数.不难发现.

另外,费马数还满足,我们考虑这个式子的证明:显然后面那一个连乘会得到若干项的次幂,并且这些项两两不同,根据几何级数,我们有=,于是显然得证.

Example1(《具体数学》4.17)

求证:如果,则.

不妨假设,有:.

Example2(《具体数学》4.18)

求证:若是质数,则是的整数幂.

如果且是奇数,我们有:.

Miller-Rabin算法

如果判断是否是质数,取,设.

则要么.

要么,使得,.

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

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

此为Miller-Rabin算法,复杂度.不保证正确性.

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

Pollard-Rho算法

对做质因数分解,若能找到使得,则考虑对和分别进行质因数分解.

考虑随机,若有个因数,那么显然随机到使得的概率为,显然不太优秀.

考虑改变随机策略,我们考虑随机一个使得,那么就是的一个因子.

这种情况下,随机的概率是,仍然很不优秀.

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

当时,错误的概率会很小,但是复杂度仍然很高,无法接受.

考虑构造.

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

显然当,则,.

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

并且在这个过程中,我们可以预处理出大量的.

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

狄利克雷前缀和

已知数列,求数列满足.

我们将一个数的质因数分解看作它的向量表示.更直接地,如果,其中是第大的质数.我们将其写作向量的形式,并做高位前缀和.

可以用的时间复杂度解决问题.

阶乘

我们定义,特别地,.

考虑估计的大小,不难发现.

而函数显然在和时取最小值,而在时取最大值.

那么我们有.

于是.

还有一种估计方式是考虑,由Stolz定理及其推论,我们知道若,那么.而我们令,,所以,于是我们可以估计.

事实上有一种更准确的估计方法:.

考虑设为中质因子的个数,我们分析一下这个函数:

首先显然有:.

我们考虑以表示在进制下各位数字之和,不妨设第位数字为.那么这个数字对于最后的答案的贡献为.求和得到.

Example(《具体数学》4.55)

令,求证:.

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

我们不妨将和分开考虑,于是显然下面的式子是上面的式子成立的充分条件:

我们不妨对上面这个式子使用数学归纳,也就是说它的充分条件是:

这个式子,当时显然成立.而当每增大的时候,左右两边同时增大,于是也是成立的,由此可以数学归纳.

互素

如果两个数和满足,我们称他们互素,记作.

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

Example1(《具体数学》4.42)

证明:如果两个分数和满足且,则的充分必要条件是.

首先,如果,显然不可能满足条件,必要性得证.

考虑充分性,如果,则只需证明即可.

而,另一个式子同理,于是得证.

Example2

证明:.

考虑:

Example3(《具体数学》4.63)

证明:满足的最小的(为第一关键字,为第二关键字)一组正整数解(即费马大定理最小的反例)一定满足以下性质:(另外,的情况早被证明了无解)

首先证明(1),如果是最小的满足条件的数但并不是质数,我们不妨设,则,显然这是更小的一组反例,于是(1)得证.

接下来考虑性质(2),注意到必然两两互质,不然可以两边同时除以一个数构造出更小的解,又注意到:

如果,那么我们有.接下来考虑每一个质因子,如果中有个,中有个,于是中有个,我们自然有:,于是满足.

如果,我们就有:,此时必有,,并且不难发现:,由于上面提到的的原因,,显然或者.下面只需要证明.

冷静一下,如果,令,此时必有:

注意到是奇数,,而,又注意到,我们把两边对取模:

注意到若,则该式子必不成立.

Stern-Brocot 树

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

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

接下来,不断地对这个序列进行以下操作:在两个相邻的分数和之间插入一个新分数.

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

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

我们不妨认为,那么不难发现这么构造序列,所得到的序列一定是单调递增的.

这是因为如果我们有,那么我们一定有:,其中,这一点不难验证.

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

然后,如果当前所得到的序列中有两个数和相邻,则,这一点不难通过数学归纳证明.而根据裴蜀定理,显然且.

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

我们考虑判断与的大小关系,这样就可以类似二分的方法一直往下找下去.

问题在于为什么我们最后一定可以找到这个数呢?如果我们一直找不到这个数,意味着无论我们怎么做,都有成立,而这也就意味着,处理一下不等式并合并,我们有.

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

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

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

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

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

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

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

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

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

我们令,,,.

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

其中:.

使用数学归纳不难证明:

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

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

如果,那么.

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

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

升幂引理

形式一

对于素数,,对于满足的:

若,则.
若,是奇数,则.

考虑(1)的证明,由于,因此.有次方差公式,显然.

(2)类似.

形式二

对于奇素数,:

若,则.
若,是奇数,则.

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

同余

如果,我们称和关于模同余,记作.

根据同余的定义,若,,我们有以下性质:

我们考虑第五条的证明:由于,则根据扩展欧几里得算法,可以求得一个数满足,也就是,那么如果我们有,只需要两边同时乘以就可以得到右边.值得一提的是,我们通常称是在模意义下的逆元,记作或.

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

考虑,设,则有,则有.

于是有,即.

现在,我们给出一个结论:数列在排序去重后恰好为数列,,而且其中每个数字在原数列中恰好出现了次.

恰好出现次是好证明的:考虑可以推导出,则显然这些数是一个序列复制次得到的.

由上,我们要证明一定是的倍数.不难发现.

接下来,不妨假设,并在此条件下证明两两不同即可.而由于,则的充分必要条件是,因此它们显然两两不同.

Example(《具体数学》4.31)

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

令表示这个数字在进制下的第位,则这条性质也就是:

不难发现,当时,满足该性质.

威尔逊定理

证明:

当为质数时，考虑对于和,若,此时可证明或(需要用到下面独立剩余知识).

如果那么一定可以在找到一对数,它们相乘为.原因是若,那么.

若不是质数,则设,当时,由于,因此一定是的倍数.

若,除非,不然一定能在里找到和,此时也是的倍数.

另外,当是奇质数的时候,威尔逊定理可以写成如下形式:

另外,通过以上推导过程,不难发现威尔逊定理还可以写成:

Example1(《具体数学》4.48)

求.

首先,类似威尔逊定理的推导,不难注意到这个式子也就等价于:

首先考虑满足的满足什么性质,根据我们在二次剩余的推导,先考虑的情况,此时我们将分解为了若干个形如的质因数的乘积,对于每个作为模数时,有两个解:和.

当的时候,显然答案就是.

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

至于的情况并没有麻烦很多,当,显然有没有这个作为质因子都一样.当,这个质因子和其它质因子并没有多少区别.

于是我们最后得到结论:

Example2(《具体数学》4.40)

如果我们设,求证:.

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

如果发生进位了,假设进到了第位,第位原本是,现在是,那么要证其对于成立,即证明下式成立:

考虑,于是上式也即:

于是化到的情况,于是时该式子成立.

Example3(《具体数学》4.53)

求所有满足的整数.

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

考虑当时,根据威尔逊定理,要求化为:.注意到此时一定不是质数,又因为,于是要求化为,显然成立.

当时,要求则化为.当时,显然不成立.反之显然成立.

于是要么,要么.

费马小定理

我们有:

根据威尔逊定理,显然可以推得费马小定理.

根据费马小定理,我们可以考虑证明一个结论:.

由于,那么我们有,也即满足,不断两边取次方即可得到上述结论.

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

考虑证明,也就是要证明.

注意到根据多项式定理,.而如果,则后面的式子在意义下显然为,不然,考虑的序列一共会出现次且每次对答案的贡献都是,自然有.

Example1(《具体数学》4.41)

求证:如果质数满足,则不存在整数满足;如果其满足,则一定存在一个整数满足条件.

先考虑证明前半部分,如果存在这样一个整数,考虑也就等价于,则.显然,根据费马小定理,我们有,也就有.

而由于,所以,所以,不符,因此一定不存在.

反之,考虑威尔逊定理的变形.由于,所以这个式子也就等价于,也就是,这就是一个解.

Example2(《具体数学》4.46)

求证:如果,则.

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

不然,设,且是的最小质因子,若,则.

若,显然不成立.不然,有,由于,则,显然不成立.

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

如果,则对于任意质数,.

中国剩余定理(crt)

对于方程组,其中两两互质,求.

令,设,是在意义下逆元.

则.

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

由于在意义下,中枚举的所有不等于的项都会成，等于的项会成.

考虑每次合并两项，显然有:,.

中国剩余定理的本质是一个环同构,当.

由于映射两边都是大小相同的有限环,所以只需证明它是单射就行.而容易发现.

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

扩展中国剩余定理(excrt)

对于方程组,若两两不互质.

我们考虑每次合并两个方程:

x\equiv a_1(\mod m_1)\

x\equiv a_2(\mod m_2)

\end{cases}

那这个方程组等价于:

x=k_1m_1+a_1\

x=k_2m_2+a_2

\end{cases}

合并上下方程,有:

设,显然若,方程无解.

不然,有:

令表示在意义下的逆元,有:

带回第一个方程:

Example1([NOI2018]屠龙勇士)

考虑拿个set之类的维护,然后问题转化为求:

的一个的最小解.

对于一个式子,设,那么若,显然无解;不然,我们有:,而,可以求逆元.

Example2([CF571E]Geometric Progressions)

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

但是直接对所有质因子做excrt复杂度不可接受.我们考虑如果对于质因子,有,显然无解.如果有,显然要么无解,要么有唯一解,而且可以快速求出唯一解是谁,直接验证就行.

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

二次剩余

求方程的解.

我们先考虑一个特殊情况:,.

那么也就相当于求方程.

如果,那么显然和只有一个能被整除,所以有.

如果,那么显然和有一个能被整除但不能被整除,另一个能被整除,如果时,显然只有一个解.当时,同上.反之,有或.考虑一个性质:.

那么如果:,也是一样的.先把作质因数分解,然后再用中国剩余定理合并,那么显然不同质数的解会累乘到总的解上,若有个不同大于的质因子,总的解的个数是.而如果考虑的情况,有个不同的质因子,则解的个数为.

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

我们称是的二次剩余,当且仅当并且,这里的是奇素数,如果不是的倍数且,则称为二次非剩余.我们引入勒让德符号来表示这个东西:

$是二次剩余为二次非剩余$

那么这玩意怎么求呢?我们有欧拉判别准则:

先证明个引理:若为意义下的原根,且,那么有解的充要条件是是偶数.

充分性显然,而必要性,我们考虑费马小定理:,而是偶数,因此无论如何奇偶性都不会变.

接下来证明欧拉判别准则:

于是得证.另外通过这个证明过程,我们可以发现中有正好一半的数是二次剩余,我们还能得知的解的数量是.

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

考虑随机一个,令,如果则放弃这次询问,不然自然有.

,注意到一定满足或,我们可以多做几次,可以理解为这样将随机分割了.

Example2(qoj5021)

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

先把模数质因数分解.

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

显然只有会出现这种情况,讨论一下全为或全为的情况,简单分类讨论可以得到共有种方案.

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

先考虑的情况:

注意到此时固定会有组(有一组全)满足条件,此时有方程.显然若,那么该方程有组解,不然只有一组解.而前者相当于满足,我们设是方程的解的数量,把上面的全部加起来,答案是:

化简一下得到:.

再考虑的情况:

注意到此时不可能有全为的二元组了.所以固定的话,共有组解,此时有方程.

若,显然当时有组解,否则无解,此时.

不然有唯一解.

而的方案有多少呢,显然是,这里用到了这篇题解的第一个双射,.

于是这里的答案就是:

化简一下得到.

现在的问题是如何求.

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

那么怎么求呢?考虑的解数为,我们有:

~~(这是干啥啊)~~

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

首先,第一步仍然是枚举其中一个,然后求另一个.然后将整个式子乘开,做一个双射就可以合并其中两项,而至于前两项则是根据欧拉判别准则直接将上指标乘起来合并.然后我们发现,因为中一半是一半是,又可以发现时显然为,,做双射.

做到这一步,自然有.

而对于的时候,我们再做双射,于是.

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

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

Example3

求和的所有解.

先看,显然是一组解.当的时候,显然有,而考虑,这自然不可能.

再看.显然和是两组解.当的时候,根据欧拉定理知道,令.自然有,这是形如的形式,只有是一个解.

BSGS

求的一组解,其中且.

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

求出,并求出所有,其中.

若.则可以直接判断是否被求出来过.

否则,则将,一直操作直到.

exBSGS

求的一组解,其中.

设,那么根据膜的性质,原方程即.

显然若并且,方程定无解.(若,那么就是一个解)

那么现在的方程就是.

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

不妨设

那么现在方程就是,可以使用BSGS求解.

ps：的时候要特判.

原根和阶

阶:找到一个最小的使得,则称是在膜意义下的阶.

原根:如果在膜意义下的阶是且,则称是的一个原根.

若有原根,则一定是,或是,其中且.

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

根据阶的定义,我们如果要判断一个不是的原根,只需判断是否使得.

而由于,因此一定有,因此只需判断的所有因数,复杂度.

事实上,只需要判断对于的所有质因子,是否有即可,复杂度.

Example1

给定,,,求的所有解,其中,.

考虑求出的原根,得到,同时由于,因此原方程变为:.

于是有:,即可求解.

Example2(《具体数学》4.47)

证明:如果,且对于所有满足的都满足,那么是素数.

首先不难发现,.

考虑上面的过程中,不可能存在一个数满足.因此.

根据欧拉定理,,因此得证.

积性函数

若函数满足,有,则称其为积性函数.若,有,则称其为完全积性函数.

若函数是积性函数并且有,则也是积性函数,证明如下:

不妨考虑数学归纳,首先.

令,则.由于归纳假设,此时只有的时候,可能不等于.

于是有

于是.

该命题的逆命题也是同样成立的.有一些常见的积性函数,比如:,,.

Example(《具体数学》4.58)

求:是的整数次幂的充分必要条件.

不难发现是一个积性函数,于是考虑.

当的时候,显然不满足条件.

不然,只有是奇数的时候,才是一个偶数.

而此时.其是的整数次幂的一个必要条件是是一个梅森素数,而且不难发现只有当的时候才满足条件.

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

狄利克雷卷积

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

交换律:.
结合律:.
分配律:.
若是积性函数,则也是积性函数.

考虑第四条的证明:

构造满足显然就是满足条件的.

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

欧拉函数

定义欧拉函数为所有满足的的个数.

令,其中.由于若,显然有且,则根据中国剩余定理,不难有,也即是积性函数.

若,则:

考虑改变枚举方式,因为,则:.

我们考虑一个事实:现在有个不同的分数,这些分数进行约分后,它们的分母即的若干因数,而它们的分子就是与这些因数互质的数,同时这些数的个数总共是个,我们可以得到:.

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

由于是积性函数,若,设,则,则有:

而,于是有,则有.

则原式等于.

和法里级数的关系

我们考虑之前提到的法里级数,令,那么的个数显然是.

接下来我们思考如何计算.事实上,我们有.这里的证明是:考虑满足的分数共有个,而如果我们枚举,那么显然右边也等于这些分数个数,于是得证.

而事实上,如果我们用来带入上面的式子,可以得到.

根据第三种莫比乌斯反演的形式,我们有:.

麦克马洪和式

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

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

那么我们显然有:

接下来我们只需要知道,当已知的时候,右边和式的贡献是多少.显然此时有,也就是,此时答案为.

为啥答案为呢?我们考虑这一定会不断在中取数,那么会取多少数呢?显然会取个数,其中,不难解得此时,因此一共有个轨道.

也就是说:.

如果我们对这个式子进行化简:

这个式子被称为麦克马洪公式.

另外,如果我们考虑这件事的证明,考虑如果,那么根据费马小定理,显然可证明.

而由于是积性函数,令,有:

我们可以通过数学归纳来证明.

Burnside定理

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

置换群:运算表示将放到位置...把放到的位置...把放到的位置,而幺元.

由麦克马洪和式的证明,我们不难推导出Polya定理:设要对个元素用种颜色染色,若通过某种旋转得到的染色方案算同一种,考虑旋转一定是一种置换,则本质不同的染色方案数,其中表示的轨道数,即有多少组置换.

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

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

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

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

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

接下来考虑置换环外:对于两个置换环间,对于一条边,我们考虑不断做置换,做多少次才能使这条边回归原位置.注意到需要做次.而总共有条边,于是轨道数量.

这样对于一个个环的置换,它的答案就是.

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

欧拉定理

当时,.

证明考虑取出中所有和互质的数,设它们为.我们有:

欧拉定理可以用来求逆元:,则有.

扩展欧拉定理

断言,其中

证明如下:

设,则要证,即证都有.

分情况讨论:

若,则为普通欧拉定理情况,即证明是的因数.由于是的因数,而是的因数,显然得证.

不然,发现且,又发现,所以,,左右两边均为,得证.

Example1(CF906D Power Tower)

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

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

同上.

Example3(《具体数学》4.54)

求.

首先,根据前面的例题,不难发现.

我们有:

由于模数现在变成了,考虑,于是我们有:

而,根据扩展欧拉定理:

Example1(《具体数学》4.57)

求证:.

先考虑将条件改为一个更好处理的式子,不难发现:

于是接下来我们要处理的式子形如.

对其增加枚举量:

带入即可证明.

Example2

求.

考虑,使用中国剩余定理,我们有:

后面那部分的答案是:

令为的原根,令,有:

考虑前面那个式子,如果我们令,,其中,后面那个式子为,由于中国剩余定理,有.

于是令上面的式子可以改为:

我们只考虑其中一项,形如:

我们不妨用代替,代替,代替,其中那么有:

则我们要做的即对四元组计数.由于,我们有:

第一个式子对四元组的贡献显然是,而第二个式子,由于,所以我们可以先求出的答案,然后乘以得到答案,是类似的,于是:

后面,由于,显然一个唯一对应一个.于是我们得到了答案为:

而后面的式子显然跟无关,所以有:

其实到这一步,由于是级别的,这题已经可以做了.

莫比乌斯函数

莫比乌斯函数是一个满足的函数,根据定义其显然是积性函数.根据定义可以求出它的封闭形式:

莫比乌斯反演

见"反演.md".

另外,值得一提的是,根据莫比乌斯反演,我们可以发现.

有公式:.原因很简单,我们设为中所有的质因子的幂先除二下取整再乘二后变成的答案,显然,我们有.

min25筛

如果我们考虑积性函数的值,理论上来说,设表示最小质因子大于等于的所有的和加上,其实我们自然有:

问题在于这么做需要枚举中的全部质数,这是根本无法接受的.

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

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

考虑:

令,其中表示最小的质因数,表示第个质数.

注意到实际上就是以内的数在第轮埃氏筛后剩余的数的的和.

表示若干完全积性函数之和且当时,,下文为了方便书写,直接认为是完全积性函数.

而实际上就是以内的质数的之和,那么有:

ps1:

第个质数会比第个多筛若干个数,即最小质因数是的数.这些数形如,同时除以得到.

我们要的就是其中最小质因数大于等于的数,也就是最小质因数大于的数,因而就是.

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

考虑到后面的维度最多走到,所以我们所枚举的最小质因子一定小于等于,所以一定有,所以直接删去一定不会多删.

ps2:

注意到以下事实:.

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

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);
    ...
}

该代码复杂度为.原因在于,根据整数分块,有种取值.

而如果递归下去,继续枚举,并往下递归到,那他就相当于枚举,并递归到,因而复杂度得到保证.

由此可知,求的复杂度为.

令表示前个数中,最小质因数大于等于的数的之和,可知:

ps1:

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

由于是当前数的最小质因子,是他的幂.则这个数其他的质因子应该均大于,因而大于等于.

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

又注意到,如果,那么此时一定小于,则不可能拥有比更大的质因子.

该形式与上面一致,因而复杂度同样为.我们最终要求的答案即.

一些后记:

事实上,复杂度的计算只是上限,实际上应该约为.
如果使用map会导致复杂度较差,考虑如下事实:

(1).,则要么,要么.

(2).形如,则应为,互不相同.

因而可以分别特判,从而做到比map或离散化都优秀的复杂度.

我们在代码中所求出的是倒序的,而我们转移的过程也是倒序的,因而枚举的时候可以直接正序枚举.
考虑做的时候由于进行了滚动数组,因而继承操作可以直接使用,为了方便可以直接判掉可以直接继承的情况.
求的过程可以使用递归,因为我们只关心一个的量.

Example1([uoj188]Sanrd)

注意到这题显然可以写埃筛的暴力.考虑使用类似min15筛的方式,定义为的次大质因子(若则),.不难发现我们要求的就是,而显然.

注意到:

区间素数个数可以拿min25筛的前半部分做.

杜教筛

令,我们考虑构造两个函数和.使得.

令.若和都很方便求,,我们就可以求出.

由于,我们有.

那么:

复杂度证明和min25筛是一样的,不同点在于我们可以预处理以内的,这样复杂度可以降到.

Example1

求.

由于,于是考虑.

Example2

求.

由于,于是考虑.

Example3

求

由于

由于中间过程中乘出来的很难处理,需要消掉它,于是考虑.

Example4

由Example3,于是考虑.

Powerful Number筛

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

现在我们要求积性函数的前缀和.假设,其中且的前缀和容易计算.

接下来我们证明:.

,,于是.根据积性函数的性质有.

注意到:

于是可以快速求,复杂度.

Example1([SP20174]DIVCNT3)

首先我们需要构造.注意到,我们构造.这样问题在于求.我们有:

而,自然可以做.复杂度算一算是.

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

整值函数

定义

若,则:

小于等于x的最大的整数.

大于等于x的最小的整数.

我们有时称为的整数部分,并定义为分数部分,有时记作.

我们定义,,其中.

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

整值函数的基本性值

若,则有:

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
分配律:.

整值函数的应用

一类函数与整值函数

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

那么,只要都有定义,我们有:

和.

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

若,显然得证;

不然,有,那么有,也就有.

考虑反证法,不妨令.则一定存在一个整数使得,此时必有.由于的性值,显然有是整数,但根据整值函数的性值,不可能存在这样一个整数满足,因此得证.

另外,我们考虑函数,显然这是一个满足条件的函数,因此显然满足上述的条件.再考虑的特殊情况:.

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

迪利克雷抽屉原理

个物体放进个盒子里,那么必定有一个盒子中放入了大于等于个物品,有一个盒子放入了小于等于个物体.

Example1

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

设为第个实数,为以这个数为开头的最长的递增子序列,表示以这个数为开头的最长的递减子序列.考虑反证法,如果不成立,那么,.那么一共有种不同的有序对.

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

Example2

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

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

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

计算区间内整数个数

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

考虑基本性值,不难发现:

包含个整数.
包含个整数.
包含个整数.
包含个整数.

谱

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

不难发现,只要,则.

Example

求证:且,即这两个集合构成了正整数集的一个划分.

我们考虑这样一个事实:对于任意正整数,如果我们能求出来中有个元素,中有个元素,并且,则结论显然成立.

不妨令函数表示中有多少个元素,其中是正数,我们有:

则我们要证明的就是:

而由于我们有恒等式:,且两个相加为整数的数的分数部分相加显然为,原式得证.

事实上,如果两个集合和构成正整数集一个划分,可以同上证明且和都是无理数.

整值函数的递归式

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

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

Example

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

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

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

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

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

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

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

假设现在进行完了轮,令,其中,则编号的时候被杀死的即是,那么之前的编号就是.

而,我们可以不断进行迭代.

如果我们令,换句话说即改变编号的顺序,我们可以有以下的赋值操作:

化简这个式子,我们有:.

事实上,我们可以证明:如果我们每隔个人就杀掉一个人的话,那么,一直迭代到时.

而最后的答案就是.

整值函数的恒等式

考虑公式,不难发现它在时的值为,而在的值为.

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

类似地,有:

用替换上面的有.

同样的,有.

整值函数的和式

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

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

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

Example1

求.

我们有:

考虑的特殊情况,则前面那一项显然是,那么:

而如果,我们令,而当的部分的贡献显然是.

于是最后的结果就是:.

另一个做法是,我们考虑增加枚举量,有:

Example2(类欧几里得算法)

求.

由于,我们有:

这样,我们将整个式子的求和分为了三部分,第二项显然是等差数列求和,而如果我们令,不难发现第三项的分子是一个等差数列重复了次,而且正因为这,第一项里面的数也就自然组成了等差数列,由于我们有恒等式,那么这一项也就自然可以计算了.

分别求和后加起来,得到答案为.

另外,对这个式子进行化简,我们可以得到:,而这个式子关于和是对称的.

也就是说:.

另外,如果要求,我们也有一种的做法(类欧几里得算法):

若,原式化为.

考虑的情况,设,原式化为

Example3

求.

上述推理过程将的情况特殊讨论了一下,不难发现,如果我们要求的式子是,也仍然可以使用将中的数特殊处理的方式做掉,因为这些数的三次根下取整一定是,式子就不难化简了.

Example4([uoj42]Sum)

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

我们有.

于是我们有:

令,根据整值函数的性质,不难发现.

于是我们有:

记,我们所要解决的问题是.如果,我们可以把整数部分取出来单独算.于是接下来我们只讨论的情况.相当于求一条斜率小于的直线下方的整点个数.我们可以反转坐标系,这样就变成了斜率大于的直线,继续做上面的操作.

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

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

解决形如的问题,其中和都是的矩阵.默认.

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

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

考虑将问题转化为:有一条的直线,我们从(不包含这个点)处开始沿直线向右走.每遇到一条横线,就进行操作;每遇到一条竖线,就进行操作.如果遇到了整数格点,就先进行操作,再进行操作.

例如上面那个例子就是:现在有一个矩阵二元组,初始为,操作是:,操作是:.一直走到的点为止,最后矩阵就是答案.不过这个形式不好写成矩阵,我们可以记录.这样最后就可以带入操作,不难发现这个操作是个环.

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

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

当时,注意到,此时任意一个操作前必然有至少个,我们令,不难发现:.

当时,我们想要让与互换,假设第个在第个之前,考虑这个前会有个,而对于后者,变换坐标系得到,由于遇到整点时,先再进行,也就是说,第个前会有个(这个并没有忽略初始位置).我们考虑如何让这个数和上面的的差分写成一样的形式.注意到需要特殊处理!

显然操作序列一共有,将二者对应一下,这里的答案就是.

然后是开头部分,开头部分一共有个和一个.

但是注意到末尾部分同样是不规整的,注意到末尾一共有个,拼到末尾即可.

最后的时候直接返回即可.

假设合并的复杂度是,注意到每层的复杂度是,但是每两层会抵消,因此复杂度.