有些坑要记一下，应该不会忘，但是随便写写

ceil(a/b) with int

如果a,b均为int/long long，那么直接使用ceil(a/b)不行，因为a/b作为中间过程是int，会被trunc。

但是使用ceil((double)a / (double)b)还是不行，因为浮点数精度不行，总有你意想不到的奇怪意外。

感觉自己像个宝崽，不会的可真多

Prefix Function (Next or Fail or whatever the same name)

KMP里用到的z[i]（prefix function，z function和prefix function可以互相转换，名字借用一下）表示字符串0…i最长相同前后缀（看了很多grandmaster代码，所有人的习惯都不一样，天知道都是怎么想的=_+，我选择保持下标一致，z[i]表示最长长度)。

通过递推，用z[0]~z[i]算出$z[i+1]$，主要思想是第i+1个字母能不能和“之前已经匹配上的最长串的下一个字母”相匹配。如果不行，递归退回次长的串，再尝试匹配。这里有个很奇妙的性质，对于当前的串0~i，最长前后匹配串长度为$z[i]$，次长为$z[z[i] - 1]$…这个套娃背后的原理是：

Not very clever to forget all these.

FenwickTree 树状数组

CHN reference from zhihu

Common data structure in programming contest to answer range query questions. Simple implementation and less functionalities, $O(n)$extra space, query and edit in $O(logn)$.

Rewind my little memories of number thoery..

GCD和辗转相除法(Euclidean Algorithm)

1
2
3

int gcd(int a,int b){
  return b?gcd(b,a%b):a;
}

Idea: old divisor $\div$ old remainder, until we have new remainder=0.