基础算法

1. 辗转相除法，求最大公约数（当然有更优化的算法，但我们要的是能满足要求，不需要回忆思考就能直接写出来的代码）

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

2. 求正整数位数

return log10(a) + 1;

3. 判断是否为偶数

return (a & 1) == 0//必须括号，因为比较运算符优先级高于位运算符
//这个不一定非要用位运算，a % 2 == 0也行

4. 判断是否为素数

bool isPrime(int a){
    if(a == 2){
        return true;
    }
    if(a < 2 || a % 2 == 0){ // 1，负数，偶数肯定不是
        return false;
    }
    for(int i = 3; i <= sqrt(a); i += 2){ // 只和从 3 开始的奇数判断
        if(a % i == 0){
            return false;
        }
    }
    return true;
}

5. 最基础的0-1背包问题
   有N件物品和容量为V的背包。第i件物品的代价是c[i]，价值是w[i]。求解将哪些物品放入背包可以获取最大价值。(要求所有值为非负整数)
   物品数和背包容量就是二维数组的大小W[N][V]。
   W[i][j]表示前i件物品放入容量为j的背包所获取的最大价值。
   状态转移方程：W[i][j] = max{W[i-1][j] , W[i-1][j-c[i]] + w[i]}