从Codeforces里面学到的一些小Trick

本文主要是来自Codeforeces里面的一篇博客。

PSA: don’t use these functions unless you really, really need to

  • 计算$\frac{a}{b}$向上取整, 直接用 (a + b - 1) / b, 不要用ceil((double) a / (double) b)
  • 计算正整数根号，不要直接使用sqrt,转而使用二分(其实这条我并不是很理解，按理说现代的sqrt的性能是没问题的，会直接翻译到硬件指令)
1
2
3
4
5
6
7
8
9
10
// works for at least up to (2**31 — 1)**2
long long int_sqrt (long long x) {
  long long ans = 0;
  for (ll k = 1LL << 30; k != 0; k /= 2) {
    if ((ans + k) * (ans + k) <= x) {
      ans += k;
    }
  }
  return ans;
}
  • 算$a^b$的时候不要用pow(a, b)，而是手动循环进行计算。
  • 计算正整数的$log_2(a)$时，不要直接使用log2(a)，而是使用基于__builtin_clz或者__builtin_clzll的方法，如果有C++20的话，也可以用bit_width的库函数。其实也就是奉劝我们从二进制表示来进行计算，而不是直接根据10进制的数学方法。