Interesting Formulas

1: \(A^{log_BC}\) = \(C^{log_BA}\)
可以把A看成\(B^x\), C看成\(B^y\), 那么原式可以变成\((B^x)^{(log_BB^y)}\) = \((B^x)^y\) = \((B^y)^x\) = \((B^y)\)^(\(log_BB^x\)) = \(C^{log_BA}\)

2: \(\sum C_k^i (i∈[0,k])\) = \(2^k\)
经典公式(?)

3: 三阶前缀和公式及推导：(非纯公式严格证明)

下面用 \(A,B,C,D\) 分别表示原数组，一阶、二阶、三阶前缀和。

讨论当 \(A_i +1\) 时对一二三阶前缀和的贡献：\((以下x都满足x \geqslant i)\)

1. \(B_x: + 1\)

2. \(C_x:+ (x-i+1)\)

3. \(D_x:\) 当 \(x=i\) 时，令 \(k=(x-i+1)=1\) ，那么对于 \(D\) ，实际上可以观察到，有 \(D_i+=k,D_{i+1}+=k+(k+1),D_{i+2}+=k+(k+1)+(k+2),...\) 拆开可发现，\(D_x+=(x-i+1)*1+(x-i+1)*(x-i)/2\) ，最终得出：

   \(D_x+=\frac{(x-i+1)*(x-i+2)}{2}\) 。

4: 平方和公式简单推导

证明 \(\sum_{i=1}^n i^2=n*(n+1)*(2n+1)/6\).

方法有很多，先记最容易的一种：

\((n+1)^3-n^3=3n^2+3n+1\)

\(n^3-(n-1)^3=3(n-1)^2+3(n-1)+1\)

\(...\)

\(3^3-2^3=3*2^2+3*2+1\)

\(2^3-1^3=3*1^2+3*1+1\)

加起来，得到 \((n+1)^3-1=3\sum_{i=1}^{n} i^2 +3\sum_{i=1}^{n} i+n\)

所以 \(\sum_{i=1}^{n} i^2=\frac{2(n+1)^3-2(n+1)-3(n+1)n}{6}=\frac{(n+1)(2n^2+n)}{6}=\frac{n(n+1)(2n+1)}{6}\)

5: 正整数 \(n\) 在 \(mod \ (n+1)\) 意义下的最小逆元是 \(n\)

很好证明，\(n*n=n*(n+1)-n \rightarrow -n+(n+1)=1\)

6: EXGCD 证明大致思路

\(ax+by=gcd(a,b)=gcd(b,a\ mod \ b)\) 进行缩小

\(=bx+(a \ mod \ b)y\)

注意这里并不是凭空造出了一个仅仅看起来像原方程的方程，而是要由构造出的方程反推出原方程的一个解：

可化为 \(ay+b(x- \lfloor \frac{a}{b} \rfloor y)\) ，那如果有一组解满足后面的新式子，就可以回推回原式，即 \(x=y', y=x'-\lfloor \frac{a}{b} \rfloor y'\)

7: 一个数能被3整除，当且仅当它的各位数的和能被3整除：

比如一个四位数 abcd , 它可以表示为 1000a+100b+10c+d = 999a+99b+9c +(a+b+c+d), 999a+99b+9*c 能被3整除不用考虑，所以只要 a+b+c+d能被3整除就能说明四位数abcd能被3整除。

8： $ \sum_{i=0}^{\infty} \frac{i}{x^i} = \frac{x}{(1-x)^2}$

9: 二进制遍历子集

https://blog.csdn.net/kdazhe/article/details/113728021

\((s-1)\&s\) 一定是 \(比s小的最大子集\)，所以如此一定可以完美遍历所有子集。

10: $ sin(A)·sin(B)=\frac{1}{2}(cos(A-B)-cos(A+B))$

11: \(sin(3A)=sin(A)*(3-4sin^2(A))\)