数论
小学奥数复习
做题前算一下时间复杂度
质数
试除法判定质数： 时间复杂度 一定 O(sqrt(n))
1) 循环条件i = 2; i <= n / i (i*i <= n潜在爆栈风险 i <= sqrt(n)太慢)

    试除法求解质因子： 时间复杂度 O(sqrt(n)) (实际logn - sqrtn)
        1) 循环所有数是否会把合数因子算进来呢？不会因为从小到大循环过程中n会被除掉的，n + 1位时再在判断条件里一定为质数
        2) 循环条件：i = 2; i <= n / i 最多只用一个大于sqrtn的质因子 循环结束后若n仍>1说明n就是剩下的这个>sqrtn的质因子特判输出

    筛质数
        朴筛：将所有数的倍数都删掉（打标记），留下的就是质数
        埃氏筛法优化：不需要删除/标记每个数的倍数，只需要将质数的倍数标记/删除即可，即在代码中将标记与判断质数放在一块 （思想会在其他题目用到）

        线性筛法（更快一点）：用最小质因子筛，因此保证每个合数只被筛一次 (基本都用线筛求质数)

        大佬详细解释：
        https://www.acwing.com/activity/content/code/content/5374176/

约数
    试除法一个数的所有求约数 类似求质因子 时间复杂度 O(sqrt(n))

    算数基本定理:
    n = p1^a1 * p2^a2 * ... * pk^ak
    约数个数
        int范围内最多1500量级个约数
        约数个数公式 = (a1 + 1)*(a2 + 1) * ... * (ak + 1)

        做法：
            因数分解
            用unordered_map/哈希表存指数和底数
            套公式

        模运算：
            (a+b) mod p=(a mod p+b mod p) mod p
            (a×b) mod p=((a mod p)×(b mod p)) mod p

    约数和
        类似求约数个数
        公式 = (p1^0 + p2 ^1 + ... + p1^a1) * ... * (pk^0 + pk ^1 + ... + pk^ak)

最大公约数：欧几里得算法 辗转相除法
    (a, b) = (b, a % b)