杂记

设\(d(x)\)为\(x\)的约数个数\(\displaystyle d(ij)=\sum_{x|i}\sum_{y|j}[gcd(x,y)=1]\)

设\(\sigma_1(i)\)表示i的约数和，那么\(\displaystyle \sigma_1(ij)=\sum_{x|i}\sum_{y|j}[gcd(x,y)=1]\frac{xj}{y}\)

简单多面体的顶点数 \(V\) 、面数 \(F\) 及棱数 \(E\) 间的关系:\(F-E+V=2\)
将二维平面看作平面图时，注意到平面图包含无限面。

\(\displaystyle \left \lfloor \frac{\left \lfloor \frac{n}{a}\right \rfloor}{b} \right \rfloor =\left \lfloor \frac{n}{ab}\right \rfloor\)

二项式反演:由\(\displaystyle g(k)=\sum_{i=k}^nC_i^kf(i)\)
可得\(\displaystyle f(k)=\sum_{i=k}^n(-1)^{i-k}C_i^kg(i)\)

枚举子集的技巧 \(for (k=j \& (j-1);k;k=j \& (k-1))\)

\(\displaystyle \sum_{p|n}\mu(p)=[n=1]\)

\(1* \varphi =id \space\space\space\space\space 1*\mu=e=[n=1] \space\space\space\space\space \mu*id=\varphi \space\space\space\space\space id*1=约数和\)

\(\displaystyle g(1)S(n)=\sum_{i=1}^{n}(f*g)(i)-\sum_{i=2}^{n}g(i)S(\left \lfloor \frac{n}{i} \right \rfloor)\)

与直径相关的结论1：与一个点距离最大的点为任意一条直径的两个端点之一。
与直径相关的结论2：两棵树之间连一条边，新树直径的两个端点一定为第一棵树直径的两个端点和第二棵树直径的两个端点这四者中之二。

对于任意的积性函数 \(f\),有\(f(gcd(a,b)) \times f(lcm(a,b)) = f(a) \times f(b)\)。

\(\displaystyle \sum_{i=1}^ni=\frac{n(n+1)}{2} \space\space\space\space\space \sum_{i=1}^ni^2=\frac{n(n+1)(2n+1)}{6} \space\space\space\space\space \sum_{i=1}^ni^3=(\sum_{i=1}^ni)^2=\frac{n^2(n+1)^2}{4}\)