Number Theory
- 如果一个质数可以表示成4x+1的形式，那么它一定可以表示成两个数字的平方和。（2是特殊情况）
- 根据欧拉常数，(M/1+M/2+...+M/M)约等于MlnM。在数论的算法中计算时间复杂度时可能会用到。
欧拉函数
欧拉函数euler(n)表示小于等于n的与n互质的数的个数，在欧拉函数，认为如果两数最大公约数为1，则两数互质。所以，n与1也互质，且euler(1)=1。
计算公式为：φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn),其中p1, p2……pn为x的所有不重复的质因数，x是不为0的整数。
欧拉函数递推求法：欧拉函数的原始公式是用n连乘（1-1/pi）。pi是n的不重复的素因子。我们可以通过一个n^2级筛法的方式去筛，这样就保证了每个合数都会被其所有素因子筛一次，只要在筛的时候在其结果上乘上（1-1/pi）即可。
Fibonacci
Fibonacci数列的通项公式中由于（sqrt(5)-1）^n太小了，所以可以忽略，无论是否忽略，n都必须大于16。
扩展欧几里德算法
扩展欧几里德算法我们可以简单的理解为求关于x，y的方程a*x+b*y=gcd(a,b)的一组整数解。用算法模板只能求出一组解，而此方程有数穷多解。设其一组特解为x0,y0。则其通解形式为：x=x0-t*b/g，y=y0+t*a/g。
其中g表示gcd(a,b)。t是一个用来协调x和y同步变化的变量。
该算法同样可用于求解a*x+b*y=c的形式的方程。方法是先求解a*x+b*y=gcd(a,b)。然后两端同时除以gcd(a,b)再乘以c即可整理出原方程的解。即a*(x*c/g)+b*(y*c/g)=c。该方程有解的条件是c能被gcd(a,b)整除。
扩展欧几里德是在欧几里德算法基础上加入了一些东西。gcd(a,b)=gcd(b,a%b) => a*x1+b*y1 = b*x2 + a%b*y2 => x1=y2; y1=x2-[a/b]*y2;
也就是原来的欧几里德在递归过程中值削减方程右侧，而扩展欧几里德要同时对左侧进行变化以求解。递归到最底层时有：b=0,gcd(a,b)=a; x=1,y=0;
除法是不支持模运算的，因此我们要将除法转化为乘法，例如除以30变为乘以30的逆元。
逆元的意思是，如果a、b互为mod c下的逆元，则a * b = 1 (mod c)。
求逆元可以用扩展欧几里德gcd(30,MOD,x,y)，把x/gcd(30,MOD)整理到0～MOD-1范围内即为30的逆元。
费马小定理
即：当p是质数且a和p互质，那么a^(p-1)=1 (mod p)
而逆元的定义是x * y=1 (mod p)则y是x的逆元。令x=a，且a与p互质，则由a^(p-1)=1 (mod p)可得：y=a^(p-2)。
对于求a的逆元这个问题，a<p且p是质数，自然可以利用上面的结论，a的逆元就是a^(p-2)。
欧拉定理
欧拉定理，对于正整数a,n，若gcd(a,n)=1，则有a^euler(n)=1(mod n)。
快速幂取模
快速幂取模算法，只要p * 2在long long范围内都可以计算，对于算法中long long * long long的情况可能超界，但是我们可以用一种类似于快速幂的方法来进行次乘法计算，即快速幂是用乘法代替幂计算以便及时取模，而此算法则是用加法代替乘法计算及时取模，把快速幂中的乘法换成加法，平方换成乘2即可。
catalan数
令h(1)＝1,h(0)=1，catalan数满足
递归式： h(n)= h(0) * h(n-1)+h(1) * h(n-2) + ... + h(n-1)h(0) (其中n>=2)
另类递归式： h(n)=((4 * n-2)/(n+1)) * h(n-1);
该递推关系的解为： h(n)=C(2n,n)/(n+1) (n=1,2,3,...)
它的适用情况有：
1、取物2n个，物品分a,b两种，任意时刻手中的a物品数<=b物品数，的方法数为h(n)。最终2n物品中，有n个a，n个b。
2、把(n+2)边形分割成若干个三角形面积组合的方法数为h(n)。
3、一圈有2n个点两两连线不交叉的方法数为h(n)。
4、有n个结点的二叉树，有h(n)种不同的构造。
stirling公式
stirling公式：lim(n→∞) (n/e)^n * (2πn)^(1/2) / n! = 1。可用来求n!的位数。
Miller-rabin
Miller-rabin算法是一个用来快速判断一个正整数是否为素数的算法。它利用了费马小定理，即：如果p是质数，且a，p互质，那么a^(p-1) mod p恒等于1。也就是对于所有小于p的正整数a来说都应该复合a^(p-1) mod p恒等于1。那么根据逆否命题，对于一个p，我们只要举出一个a（a < p）不符合这个恒等式，则可判定p不是素数。Miller-rabin算法就是多次用不同的a来尝试p是否为素数。
但是每次尝试过程中还做了一个优化操作，以提高用少量的a检测出p不是素数的概率。这个优化叫做二次探测。它是根据一个定理：如果p是一个素数，那么对于x(0 < x < p)，若x^2 mod p 等于1，则x=1或p-1。逆否命题：如果对于x(0 < x < p)，若x^2 mod p 不等于1，则p不是素数。根据这个定理，我们要计算a^(p-1) mod p是否等于1时，可以这样计算，设p-1=(2^t) * k。我们从a^k开始，不断将其平方直到得到a^(p-1)，一旦发现某次平方后mod p等于1了，那么说明符合了二次探测定理的逆否命题使用条件，立即检查x是否等于1或p-1，如果不是则可直接判定p为合数。
pollard-rho
这是一个用来快速对整数进行质因数分解的算法，需要与Miller-rabin共同使用。求n的质因子的基本过程是，先判断n是否为素数，如果不是则按照一个伪随机数生成过程来生成随机数序列，对于每个生成的随机数判断与n是否互质，如果互质则尝试下一个随机数。如果不互质则将其公因子记作p，递归求解p和n/p的因子。如果n是素数则直接返回n为其素因子。
小于等于x的质数的个数是log(x)级的。
c(n,k)(k<=n)的奇偶性取决于(n-k)与k的二进制表达式是否存在同一位上的两个数码均为1，若存在，则为偶数，反之为奇数
使用lowbit，即二进制码中的最靠后的1和后面的0组成的数字，加上或减去这个就相当于把数字归结到左侧最近的或者右侧最近的2的x次幂整块上，x刚好大于该数的含有因子2的个数。
约瑟夫问题
约瑟夫问题，有n个人站成一圈，依次编号0～n-1，编号为(m-1)%n的人出局，然后剩下的n-1个人重新编号，让原来在m后面的那个人编号为0，剩下的依次递 增，编号从1～n-2。再次让编号为(m-1)%(n-1)的人出局。不断重复此过程，直至只剩一个人为止。问这个人在第一次编号时的编号。想要解决约瑟夫问题我 们要逆推。试考虑刚才过程的逆过程。当前剩余x人且已编号，逆过程也就是把那个刚刚出局的人重新加进圈里来，并还原上一次的编号。我们需要做的是在当前x 人中的编号为0的那个人前面插入一个人，让那个人的编号为(m-1)%(x+1)，其余人的编号可根据这个新加进来的人的编号来确定。我们要从最后剩一个人的情况 开始逆推到剩余n个人的情况。我们只需要让那个最终胜利的人的编号按照逆过程的编号变化规律进行变化即可。其变化规律为，设原来获胜者序号为a，加入一个 出局的人之后人数为x，则现在获胜者的序号应当变为(a+m)%x，即让序号跟原来比错位了m个人。总结成递推公式：f(n)=(f(n-1)+m)%n
要求用两两交换的方式给一个数列排序，交换f[i]和f[j]的代价为f[i]+f[j]，求最小代价。具体方法就是在数列中找置换环，每个环有两种处理方式，一种是用最小的元素将环里所有元素归位，另一种是用全数列最小元素与环内最小元素交换，并在环内用这个全数列最小元素将环里所有元素归位，再与原环内最小元素交换回来。