数据结构与算法笔记

考完蓝桥杯，混完省三参与奖，开始重新补数据结构与算法，目标是Leetcode Knight

数学相关算法

LCM(最小公倍数)

使用公式LCM(a, b) = |a * b| / GCD(a, b)
然后使用辗转相除法球的最大公约数

1. b = 0, GCD = a;
2. a = b, b = a % b, 递归至b = 0;

   int gcd(int a, int b){
       while(b != 0){
           int temp = b;
           b = a%
       }
   }

   可以看作是一个长方形，长边是a，短边是b。如何使用一个正方形将该长方形填满，所求的最大的正方形边长就是a和b的最大公约数。
   先使用

   小技巧
   需要将一个数字按位分离，可以使用to_string()函数

快速幂

int quick_power(int x, int pow){
    int res = 1;
    while(pow){
        if(pow & 1) res *= x;
        pow >>= 1; //注意是>>=，忘了等号会死循环，忘好几次了。
        x *= x;
    }
    return res
}

快速幂的原理都很清楚，可是对一个更大的数求快速幂需要使用到取余的操作，这里对取余操作写下思考。

(a * b) % m = ((a % m) * (b % m)) % m
(a ^ b) % m = ((a % m) ^ b) % m

对应的快速幂代码是

//这里是对1337取余
int quick_power(int x, int power) {
    int base = x % 1337;  // 先对a取模，避免a太大
    int res = 1;
    
    while (power) {
        // 如果当前指数为奇数，乘入res
        if (power & 1) {
            res = (res * base) % 1337;  // 这里取模，避免溢出
        }
        // 计算base的平方，并取模
        base = (base * base) % 1337;
        
        // 右移一位，指数减半
        power >>= 1;
    }
    
    return res % 1337;
}
//对每个数字的多次取余并不会影响结果，反而会使数字控制在范围之内，最后在所有的乘法后return时最后取余即可完成公式的最后括号外的取余

小技巧
一个数字可以分数位求幂，例如2 ^ 123，可以求{2 ^ 3} * {(2^10) ^ 2} * {(2^100) ^ 1}