Gcd 与 Lcm

\[ \text{lcm}(S)=\prod_{T\subseteq S}\gcd(T)^{

{(-1)}^{|T|+1}}\\ f(n)=af(n-1)+bf(n-2),\gcd(a,b)=1 \\ \gcd(f(x),f(y))=f(\gcd(x,y))\\ \gcd(x^a-1,x^b-1)=x^{\gcd(a,b)}-1 \]

欧拉定理

\[ a^{\phi(p)}=1 (\text{mod } p)\ (\gcd(a,p=1)) \]

扩展欧拉定理

\[ a^b=a^{\min (b\%\phi(p)+\phi(p),b)}(\text {mod }p) \]

中国剩余定理

\[ \forall i<j \le n\ \gcd(b_i,b_j)=1\\ \begin{cases} x≡a_1\mod b_1\\ x≡a_2\mod b_2\\ ...\\ x≡a_n\mod b_n\\ \end{cases}\\ x=\sum_{i = 1}^na_i\times ans_i\times\prod_{j=1}^n b_j\times\frac 1 {b_i} \]

扩展中国剩余定理

\[ ∃ i<j \le n\ \gcd(b_i,b_j)>1\\ \begin{cases} x≡a_1\mod b_1\\ x≡a_2\mod b_2\\ \end{cases}\\ x=b_1x_1+a_1=b_2x_2+a_2\\ b_1x_1+(-b_2)x_2=a_2-a_1\\ x=b_1x_1+a_1 \mod \text{lcm}(b_1,b_2) \]

卢卡斯定理

\[ p\in \rm Prime \\\binom n m =\binom {\lfloor\frac n p\rfloor}{\lfloor\frac m p \rfloor}\times\binom {n\text{ mod }p}{m\text{ mod }p} \]

扩展卢卡斯定理

\[ P = \prod_{i = 1}^np_i^{k_i} \\ \binom n m=\frac{\frac {n!}{p_i^{u}}}{\frac {m!}{p_i^{v}} \frac{

{(n-m)!}}{p_i^w}}\times p_i^{u-v-w}\mod p_i^{k_i}\\ \text{Let } f(n)=\max(x) \text{ makes }n!\mod p_i^x=0\\ g(n)=\frac{n!}{p_i^{f(n)}}\\ f(n)=f(\lfloor\frac{n}{p_i}\rfloor)\times\lfloor\frac{n}{p_i}\rfloor\\ g(n)=g(\lfloor\frac{n}{p_i}\rfloor)\times \frac{p_i^{k_i}!}{p_i^{u_1}}\times \frac {(n \text{ mod }p_i^{k_i})!}{p_i^{u2}} \\ \text{Finally just merge each ans for mod }p_i^{k_i} \text{ by CRT.} \]

BSGS 算法

\[ a^x=b\text{ (mod p)}\\ x = pm-q\ (m=\sqrt p)\\ a^{pm-q}=b\text{ (mod p)}\\ a^{pm}=b\times a^q\text{ (mod p)}\\ \]

扩展 BSGS 算法

\[a\times b\text{ mod } p=\frac a d\times \frac b d \text{ mod } \frac p d\\ \text{Let d = gcd(a, p)}\\ a^{x-1}\times\frac a d = \frac{b}{d}(\text{mod } \frac p {d})\\ \text{Specially When b = 1, x = 0.}\]

组合数

\[\binom n m =\binom {n - 1} m+\binom {n - 1}{m - 1}\\ \sum_{i = 0}^n\binom n i=2^i \\ \sum_{i = B}^{n} \binom i B=\binom {n + 1} {B + 1}\\ \binom n {a + b}=\sum_{i = 0}^n \binom i a \binom {n - i } b\\ \binom n m =\sum_{j = 0}^m \binom {n - m - 1 + j} {j} \]

二项式定理

\[(a+b)^n=\sum_{i = 0}^n \binom n i a^ib_{n-i}\]

二项式反演

\[f(n)=\sum_{i = 0}^n \binom n ig(i)→g(n)=\sum_{i = 0}^n(-1)^{n-i}\binom n i f(i)\\ f(k)=\sum_{i = k}^n\binom i kg(i)→g(k)=\sum_{i = k}^n(-1)^{i-k}\binom i k f(i)\]

上升幂与下降幂

\[x^{\underline{k}}=\prod_{i = 0}^{k-1}(x-i),x^{\overline{k}}=\prod_{i = 0}^{k - 1}(x+i)\\x^{\underline{k}}=\binom x k\times k!\]

斯特林数

\[\genfrac{[}{]}{0pt}{}{n}{m}=(n-1)\genfrac{[}{]}{0pt}{}{n-1}{m}+\genfrac{[}{]}{0pt}{}{n-1}{m-1}\\ \genfrac{\{}{\}}{0pt}{}{n}{m}=m\genfrac{\{}{\}}{0pt}{}{n-1}{m}+\genfrac{\{}{\}}{0pt}{}{n-1}{m-1}\\ \genfrac{\{}{\}}{0pt}{}{n}{m}=\frac 1 {m!}\sum_{k = 0}^m(-1)^k\binom m k (m-k)^n\\　 x^{\overline n}=\sum_{i = 0}^n \genfrac{[}{]}{0pt}{}{n}{i}x^i,x^n=\sum_{i = 0}^n\genfrac{\{}{\}}{0pt}{}{n}{i}x^{\underline{i}}\\ x^{\underline n}=(-1)^n(-x)^{\overline n}\\ x^{\underline{n}}=\sum_{i = 0}^n(-1)^{n-i}\genfrac{[}{]}{0pt}{}{n}{i}x^i,x^n=\sum_{i = 0}^n(-1)^{n-i}\genfrac{\{}{\}}{0pt}{}{n}{i}x^{\overline i}\\ n!=\sum_{i = 0}^n\genfrac{[}{]}{0pt}{}{n}{i} \]

斯特林反演

\[f(n)=\sum_{i = 0}^n\genfrac{\{}{\}}{0pt}{}{n}{i}g(i)→g(n)=\sum_{i = 0}^n(-1)^{n-i}\genfrac{[}{]}{0pt}{}{n}{i}f(i)\]

常见积性函数

\[ \text{Let n = }\prod_{i = 1}^mp_i^{k_i}\\ e(n)=[n=1]\\ I(n)=1\\id(n)=(n)\\ \mu(n)=[\max_{i = 1}^m(k_i)\le1](-1)^m \\ \phi(n)=\sum_{i = 1}^n[\gcd(i,n)=1]\]

狄利克雷卷积

\[(f*g)(n) = \sum_{d|n}f(d)g(\frac n d)\\ f*g=g*f\\(f*g)*h=f*(g*h)\\ (f+g)*h=f*h+g*h\\f*e=f\]

积性函数相关套路

\[\sum_{d|n}\mu(d)=[n=1],e=\mu*1\\ \sum_{d | n}\phi(d)=n, \phi*I=id\\ \sum_{d|n}\frac {\mu(d)}{d}=\frac {\phi(n)} n,\phi=\mu*id \]

杜教筛

\[f*g=h,\text{How to get the sum of f.}\\\sum_{i = 1}^nh(i)=\sum_{i = 1}^n\sum_{d | i}f(d)g(\frac i d) \\ \sum_{i = 1}^nh(i)=\sum_{d = 1}^ng(d)\sum_{k = 1}^{\lfloor\frac n d\rfloor}f(k) \\ \sum_{i = 1}^nh(i)-\sum_{d = 2}^ng(d)\sum_{k = 1}^{\lfloor\frac n d\rfloor}f(k) =g(1)\sum_{i = 1}^nf(i) \]

FFT 共轭优化

\[F(a+bi)=F(a)+iF(b)\\ (\overline{F(a+bi)})'=F(a)-iF(b)\\ \]