数学在算法中的运用

1. 在C++中负数取余位了避免出现负数运用==同余定理==

   x%mod=(x%mod+mod)%mod

2. 路灯覆盖问题：一个灯可以照亮+-k的区域，路的长度为l，需要的最少路灯数量为多少？

   n = l / (2k+1) 上取整，即n = (l + 2k + 1 - 1) / (2k + 1)

3. ==欧几里得算法==：两个整数的最大公约数等于其中较小数与两数的差的最大公约数

   int gcd(int a, int b) {
       if (b == 0) {
           return a;
       } else {
           return gcd(b, a % b);
       }
   }
   int gcd(int a, int b){
       return b ? gcd(b, a % b) : a;
   }

4. ==裴蜀定理==：对于任意整数x,y, ax+by都一定是d的倍数

   ax + by = gcd(a,b)

​ note：0 和x的最大公约数为x