低于On的算法

快速幂Ologn

辗转相除法 Ologn

分解质因数 O√n （对称，成双成对出现）

分块检索法 O√n （可以找到次优解，最优解可能是logn的算法）

快速幂

取模运算：+-*满足

递归的写法，最不容易写错

int fastPower(int a, int b, int n) {
    if (n == 1) {
        return a % b;
    }
    if (n == 0) {
        return 1 % b;
    }
    
    long product = fastPower(a, b, n / 2);
    product = (product * product) % b;
    if (n % 2 == 1) {
        product = (product * a) % b;
    }
    
    return (int) product;
}

二进制的做法---非递归，比较巧妙

int fastPower(int a, int b, int n) {
    long ans = 1, tmp = a;
    
    while (n != 0) {
        if (n % 2 == 1) {
            ans = (ans * tmp) % b;
        }
        tmp = (tmp * tmp) % b;
        n /= 2;
    }
    
    return ans;
}

就是二进制转换

分块检索

将长度为N的区间分成√N的大小的小区间

总共 √N 个小区间，每个小区间统计局部的数据

因此在这些区间中进行增删查改的效率是 O(VN)

链表不支持二分法（因为不支持下标访问）

线段树可以做（标准的做法）

On√range