若a,b为两个整数，且它们的差a-b能被某个自然数m所整除，则称a就模m来说同余于b,或者说a和b关于模m同余

记为a=b(mod m)(同余符号懒得弄了，暂时就拿等号代替)

还有一种理解同余的说法，那就是两个数把多余的部分（大于模数的部分）砍掉，剩下的数值一样，那么我们就说这两个数同余

对于整数a,b,c和自然数m,n, 对模m同余具有以下一些性质

那么显然我们可以得到，sp=tq,因为p,q互质，所以一定存在s=kq

但是此处却说不满足，可见并不是逆元乘法当除法？

所以这里是一个有疑惑的地方

关于同余这里有一个快速的指数取余的算法

那就是快速幂，快速幂基于两个事实，我们可以在log的时间把一个数分解成2进制

对于二进制的偶数次幂，我们可以直接利用结果，奇数次幂可以用a*偶数次幂，也就是基于偶数加一等于奇数这一基本事实

所以我们可以组装成任意的幂次，注意特判b=0的情况

根据定理1，对于方程a*x+b*y=c,我们可以先用扩展欧几里得算法（EXGCD）求出一组x0,y0,

我们知道它的解一定存在，那么根据上述的某一条性质我们可以得出结论,a/GCD(a,b)与b/GCD(a,b)互质

并且我们知道GCD(a,b),的含义在这里是能够整除a,b的最大约数，如果约数比GCD(a,b)还大，那么a,b至少有一方不能被此约数整除

我们在求出特解x0,y0时，向所有解推广时，运用了上面一个显然的事实

但是这里k取整数则会漏解，因为我们知道要想这个式子成立，x0需要加上一个b为分子，能整除a,b的的数作为分母

y0需要减去一个a为分子，能整除a,b的数作为分母，（这两个分母当然取一样的）这样才能满足等式

但是我们知道能整除a,b的数非常多，but 我们知道了能同时整除a,b最大的数，我们取这个数作分母

k取任意整数就能获得所有解，你担心漏掉a,b其他公共约数作为分母的情况的解？不存在的，因为k是任意的

k能枚举所有其他公约数为分母比(例如b/GCD(a,b))大的部分的所有因子的情况，所以这有点类似于基元的思想

所以我们来推一下这个解最终的形式应该是怎么样的，要求ax+by=c的解

但在实际问题中，我们往往被要求去求最小整数解，也就是一个特解，

那么为什么这样就能求出最小整数解呢

因为所有解的形式后面都带B*k,或者A*k,我们把这些都%掉

就剩下最小的X0,Y0,然后我们知道%剩下的这些一定小于B或A（取模运算）

那么如果此时（c语言%运算）%的结果小于零，但是它的绝对值的结果一定小于B或A

此时我们再给他加上B或A，所以我们求出的是最小非负整数解

那么我们只需跑一趟EXGCD就能算出来a的逆元是多少

求逆元还有一个线性算法，具体过程如下

然后我们设p=k*i+r,是p/i的带余除法，令i>1&&i<p,令p是质数，那么所有i都与p互质，都互质那么就都存在逆元

然后我们显然可以知道r<i，这意味着r也是存在逆元的,再将这个式子放到mod p的意义下

在两边同时乘上i^-1,r^{-1就会得到}

因为我们不想得出一个小于零的结果，我们知道

这就是线性求逆元的递推式子了

实际上这也提供了一种O(logn)底数为2，

的时间内求出单个数逆元的方法，只要直接按照那个公式递归就可以了。可以证明p mod i<i/2

每次递归问题规模减半，最终只会有O(logn)次递归，GCD貌似只需要位数乘5的复杂度，这个要比GCD快一个常数

我突然想到了GCD和线性差分方程，然而线性差分方程又和斐波那契数列有关（斐波那契数列是线性差分方程的一种特殊形式）

GCD为什么和线性差分方程有关呢

这不就是典型的差分形式么

任意正整数都有且只有一种方式写出其素因子的乘积表达式

这里有一个显然但是容易忽略的事实

这个很好理解，因为A的所有因数必然是A中所有素因子及其幂次的组合(与顺序无关所有和排列没有关系)

这个非常好理解，因为如果a=km+r,则你先%m对答案无影响

如果k=0,也是没有影响的

但是我们需要对A本身就是一个素数进行特判

求A^B的所有约数之和

对于每一个pi我们需要

本质就是我们提出来一个因子使得问题的规模缩小一半

n分奇偶来讨论，如果n是奇数则一共有偶数项比如说n=7

其实我们发现如果n是奇数。。则都是满足这个规律的

如果n是偶数，比如说n=8

所以这样我们就能递归求解等比数列和了

在模N同余的意义下有唯一解

 仅仅是这个结论，它并不显然，但是只要我们能构造出解，就证明了这个结论

由于诸mi两两互素，这个方程组作变量替换，令x=(N/mi)*y

答案超过N怎么办。。我们边算边模就行了

斐波那契数列，常系数差分方程，待定系数法求通解

这是这种方程的通解，然后对于项数很大的常系数差分方程，我们可以利用矩阵快速幂

　　　　　　　　(b　　 0)

然后依次类推就行了，就能一直算出后面的项

求卡特兰数列的第n项，可以用如下几个公式

在数据范围比较小的情况下，我们可以sqrt(N)判断一个数是不是素数，如果数据规模是S则总共需要S*sqrt(S)才能判别所有数，非常慢

它的原理就是考虑所有<=sqrt(N)的N的约数，为什么不考虑>sqrt(N)的约数？因为如果一个约数大于sqrt(N)那么另外一个约数必定小于sqrt(N)

对于数据范围较大的情况，我们需要素数筛法

一个经典的素数筛法是这样的，

先将2~N（1不是素数不考虑）之间所有数写在纸上，

在2的上面画圈，然后划去2的其他倍数，第一个既没有画圈也没被划去的数是3

在3的上面画圈，然后划去3的其他倍数

重复上面这个过程，知道<=N的所有数都被考虑过画圈还是被划去

i是过程中第一个既没有画圈也没被划去的数

其中我们在枚举i的倍数时，只需从i*i开始筛，因为k*i(k<i)的情况已经被考虑过

从上述算法我们可以发现事实

该算法会造成重复筛除合数，

所以这里有了一个线性的筛法

首先，明确一个条件，任何合数都能表示成一系列素数的乘积

1.如果i是素数的话，那简单，一个大的素数i乘以不大于i的素数，这样筛除的数跟之前的是不会重复的

这种筛法的关键就在于，当我们判断p1==prime[j]的时候，不再进行筛除，开始下一轮

什么时候判断p1==prime[j]呢，由于prime数组单调递增(从小往大筛除顺序决定的)

可以直观地举个例子，当i=2*3*5,我们可以筛去2*i,但是没有必要筛除3*i

如果i'=3*3*5,由于i'%2!=0,所以2*i'一定被筛去，但是3*i==2*i',即可以表示成一个更大的合数和一个更小的质数的乘积

这个终止条件我们还可以这么看待，i%prime[j]==0

所以仍然是避免了下一个筛除的数可以表示成一个更大的合数和更小的质数的乘积

而且我们知道这个算法的核心就在于

每个数我们只用他最小的质因子去筛除

1.一个数不会被重复筛除

 为什么一个数不会被重复筛除呢。。还是基于前面对数字的唯一表示法的限定

我说的这个唯一表示法是什么呢，就是我们知道一个数可以被分解成唯一素因子的幂次的乘积的形式

但是如果这么多散开的因子(2^3散开就是2*2*2),不按照固定的规则排列，那么显然有n!的排列方式(这里只是粗略地算了一下，实际应该是可重集合排列

所以这样不行，我们把它所有素因子全部排序。。那么他就可以表示成i*a,i是它最小的素因子，a当然不用管啦，我们把它内部看成有序的不就好了吗

当然a的最小素因子是大于等于i的，

所以在筛2*3*5时，为什么不筛素因子3,5呢，筛3的话会筛掉3*2*3*5,然而这和排序后的2*3*3*5是等价的，素数2可以轻易处理这种情况

筛5呢，5*2*3*5,然而和排序后的2*3*5*5等价，3*5*5遍历2时即可处理，当前处理则是不明知的重复劳动

内循环有一个细节，i*pr[j]<maxn，如果没有这个。。不仅会多跑。。而且可能会越界re

假设合数不能被筛除，则说明合数不能表示成最小质数i*a(最小质数大于等于i的数)，这显然是不成立的。。但是我感到这是不严谨的，，后续再补

威尔逊定理的逆定理也成立

q只能等于0，所以每个(等会这个也是错的)

两边同乘以a的逆元可以得到

并且mod p的结果有p个0~p-1，但是没有0,所以就剩下p-1个，然而这p-1个结果还各不相同，

所以说这p-1个数对模p的同余结果一定是，1,2,3,...,p-1的某种排列

由于(p-1)!和p显然互质，所以(p-1)!的逆元一定存在

其实这是一种特殊情况，一般情况下，若p为素数，则a^p=a(mod p)

这就是著名的费马小定理

　说Miller-Rabin测试以前先说两个比较高效的求a*b% n 和 a^b %n 的函数，这里都是用到二进制思想，将b拆分成二进制，然后与a相加（相乘）

下面这个方法还有另外一个名字，俄罗斯乘法(雾)

 当相乘的两个数在long long 范围内的时候我们可以使用O(1)乘法

　　费马小定理：对于素数p和任意整数a，有a^p ≡ a(mod p)（同余）。反过来，满足a^p ≡ a(mod p)，p也几乎一定是素数。

　　伪素数：如果n是一个正整数，如果存在和n互素的正整数a满足 a^n-1 ≡ 1(mod n)，我们说n是基于a的伪素数。如果一个数是伪素数，那么它几乎肯定是素数。

　　Miller-Rabin测试：不断选取不超过n-1的基b(s次)，计算是否每次都有b^n-1 ≡ 1(mod n)，若每次都成立则n是素数，否则为合数。　

注意，MIller-Rabin测试是概率型的，不是确定型的，不过由于多次运行后出错的概率非常小，所以实际应用还是可行的。（一次Miller-Rabin测试其成功的概率为3/4）

前边说的伪代码实现很简短，下面还有一个定理，能提高Miller测试的效率：

可以利用二次探测定理在实现Miller-Rabin上添加一些细节，具体实现如下：

　　前边这个算法经过测试还是比较靠谱的，可以用作模板。本菜也找过其他模板，可是有的居然把9测成素数，汗 -_-!

尊重作者：AC_Von 原创，转载请注明出处：

费马定理是用来阐述在素数模下，指数的同余性质。当模式合数的时候，就要应用范围更广的欧拉定理

欧拉函数：对正整数n,欧拉函数是小于等于n的数中与n互质的数的数目

也就是说一共有p^(a-1)-1个数能被p整除，从而不与p^a互质

为正整数n的素数幂乘积表达式

证明:由于诸素数幂之间是互质的，根据引理1得出:

首先，对于任意一个偶数，我们都可以提取出一个2的质因子，如果结果仍然为偶数，则可继续该操作

直至其化为一个奇数和2的多少次幂的乘积，

那么我们可以假定这个奇数可以被表示为N=2*n+1,如果这个数是合数，那么一定可以写成N=c*d的形式

不难发现式子中的c,d都是奇数，否则N是偶数，不妨设c<d,c=d怎么办，c=d我们则可以写成c=1,d=N=c*d,这样就好了

这正是Fermat整数分解的基础

那么我们就枚举大于N的完全平方数a*a

计算a*a-N的值，判断计算的结果是否是一个完全平方数，如果是的话，则a+b和a-b都是N的因子（因为N=a^2-b^2=(a+b)*(a-b)=c*d）

然后我们就可以将算法递归地进行下去，直到求出n的所有质因子

pollard-rho。是一个寻找n的因子的方法。基于这个事实：如果a不为n的倍数，那么gcd(a,n)为n的一个因子。

II、利用函数计算出x2使得x2-x1不被n整除。

所以这里这个显然但是容易忽略的事实，如果a不为n的倍数，那么gcd(a,n)为n的一个因子。派上大用场了。。

实践中通常取c=1,即b=a*a+1,在下一次计算中，将b的值赋给a,

再次使用上式来计算新的b值，当a,b出现循环时，即可退出进行判断，当然初值由自己确定，

但是这样的话判断循环比较麻烦，我们可以用另一种方法。

是由Floyd发明的一个算法，我们举例来说明这个聪明又有趣的算法

假设我们在一个很长很长的圆形轨道上行走，我们如何知道我们已经走了一圈呢，当然我们可以像第一种方法那样做

更聪明的方法是让A和B按照B的速度是A的两倍从同一起点开始往前走，当B第一次赶上A时，（套圈，因为B在第一圈之内一定无法和A相遇除非速度一样）

我们便知道B已经走了至少一圈。

所以我们可以把x当作B,y当作A来进行循环测试，具体实现详见参考程序

先来说一下欧拉函数的线性筛法

我们要证明的是其中要用到的一个结论，

我们可以取证明过程中的一个结论。。那就是E(p^k)=E(p^(k-1))*p,实际上这是一个显然但容易忽略的事实

这里我们考虑了在线性筛中i%pr[j]==0的情况，互质的情况呢

显然如果没有碰到i%pr[j]==0的情况时，这个合数(质数就不用考虑了),还没有遇到和他最小的质因子相等的质数，那么又唯一分解定理可知，这些情况

两个数都是互质的 

有一个显然但是容易忽略的事实，A>0,A如果不是C的倍数，A一定小于C，（如果C是质数那么A和C一定互质）

先来了解一个概念：离散对数，离散对数是一种在整数中基于同余运算和原根的对数运算。

并不是每一个模都存在原根。。

因为C是质数，如果A是C的倍数则B=0，否则A<C,则A，C互质

则A的幂次mod C有循环节(欧拉定理)，所以x是这个范围的

这个算法是以空间换时间，对穷举算法的一个改进

原始的BSGS只能解决C为素数的情况

如果我们枚举i,j则这是sqrt(C)*sqrt(C)的，但是这样我们就枚举出了所有的x,由此可知该枚举方法的正确性

其实就是。。我们需要枚举小于sqrt(C)和大于sqrt(C)的情况

但是我们可以只枚举i,这是sqrt(C)级别的枚举

由于A,C互质，则A的幂次也和C互质，所以相当于求Dx+Cy=B

所以跑一遍扩展欧几里得算法，我们就能算出A^j是多少

求出了A^j,现在的问题就是我怎么知道j是多少，一个非常聪明的方法是，先用sqrt(C)的时间

将A^j全部存进hash表里面，然后查表只需O(1)就知道j是多少了，当然这里是手工Hash的复杂度

关于消因子，是这样的，

 然后我们又可以推出

那么由于是充分必要条件，我们也可以反推回A=B(mod m)

那么如果AC，和mC有公因子，这个情况显然有公因子C嘛，于是我们可以消去公因子，那么BC也要消去同样的公因子C

扩展的BSGS不要求C是素数，大致的做法和原始的BSGS一样

只是做一些修改，因为同余具有一条性质

显然d能整除a*d,那么d也能整除k,如果d不能整除k就无解

进一步分析我们可以知道假如A是小于d的，那么K<d,（mod Cd）

假如A是d的倍数，那么mod C*d是绝对不会剩下一个比d还小的数，

并且这个数一定是d的倍数，刨去单个的d,同理不会剩下比d小的数，所以一定是d的倍数，所以一定会被d整除

后面做法就跟BSGS一样了。

所以在消因子之前需要做一次log（C）的枚举，直接验证A^i%C=B

据说这样是要考虑到ρ型轨道，问题来了，，轨道是什么呢

那个轨道是这样，因为n^x mod p 的值最终会产生循环，所以你可以想象各种轨道就好像循环的链表！

因为phi(m)是循环节结尾，如果有比phi(m)小的循环节尾，那么那个数一定可以整除phi(m)

所以我们在log(phi(x))的时间里能够判别a是否是x的原根

 1 假设x-1可以分解为p1~pm的幂次，Si=(x-1)/pi;
 那么假设a的S1~Sm幂次存在一个等于1的数，那么显然这个不是我们要的答案，因为他构成互不相同的元素集合
 2 那么如果a的S1~Sm次方都没有等于1的，此时我们用反证法来证明再没有因子能使得a的幂次等于1
12 （而我们知道一个数被分解质因数之后，他的因子必能写成他的质因子的乘积，故因子最小为p1~pm
 所以比x-1小的尽量包含尽可能多因数的情况最多有多少种呢，显然让他减去最小的质因子的一个幂次就可以也就是，x-1/pi）
17 那么这个假设与Si中没有能使a^Si=1的前提矛盾，故，在任意a^Si!=1时，再也没有比x-1小的数t能使a^t=1