入门数学知识

一、数论
    1.质数
        定义： 在大于1的整数中，如果只包含1和本身这两个约数，就被称为
质数（素数）。
        (1).质数的判定--试除法。   O(sqrt(n))
            设n为被判断数，d为其约数，可以得到另一个约数为n/d，
        故约数是成对出现的，所以判断条件可以只循环到n的平方根。
        (2).分解质因数--试除法。    O(sqrt(n))
            从小到大枚举n的所有数i，如果n和i相模等于0，就把出现的次数存下来。
        (3).朴素筛法               大概O(nlogn)，计算需要知道调和级数
            从2开始，把每个数的所有倍数删掉。最后留下来的数是质数。
        (4).筛法简单优化--埃氏筛法  大约O(nloglogn)
            把朴素筛法中的从2开始枚举换为从2开始，只筛质数的倍数。
        质数定理：1-n当中有n/（ln n）个质数。
        (5).线性筛法
            核心：n只会被它的最小质因子筛掉。
            ① i%pj == 0
                pj一定是i的最小质因子，pj一定是pj*i的最小质因子。
            ② i%pj != 0
                pj 一定小于i的所有质因子，pj也一定是pj*i的最小质因子。
    2.约数
        (1).试除法求一个数的所有约数
            
        (2).约数个数
            基于算术基本定理。
            公式。
        (3).约数之和
            公式。
        (4).欧几里得算法（辗转相除法）
            

    3.欧拉定理
        (1).欧拉函数 φ(n) 1~n中与n互质的数的个数。
            （待更新公式）
            公式的证明应用到了容斥原理。
            容斥原理推导欧拉函数：
                ①：从1-n中去掉p1、p2……pk所有的倍数。
                ②：有些数被减去了两次次，加上所有pi*pj的倍数。
                ③：减去所有pi*pj*pk的数（减了三次又加了三次，相当于没变）
                ④：以此类推。
        (2).欧拉定理：
                若a与n互质，则a^φ(n)≡1(mod n)

    4.快速幂
        能够快速的求出来a^k mod p     时间复杂度O(log k)
        核心思路：反复平方法。
        原理：

    5.扩展欧几里得算法
        裴蜀定理：对于任意正整数a,b，一定存在整数x,y，使得
                        ax+by=(a,b)
        
    6.中国剩余定理

    7.高斯消元
        在O(n^3)之内求解一个包含n个方程和n个未知数的多元线性方程的解。
        利用初等行列变换……

        高斯消元：
            枚举每一列，设为c
                ①找到绝对值最大的一行
                ②将该行换到（未固定的行中的）最上面
                ③将此行此列的数变成1（系数）
                ④将下面所有行的第c列消成0


    8.组合计数
        递推方式O(n^2)，预处理方式O(n logn)（!），卢卡斯定理,卡特兰数。  
        
    9.容斥原理
        
    10.博弈论