数学模型

莫比乌斯反演与筛法

[g(n)=sum_{d|n}f(d)$$ $$f(n)=sum_{d|n}{mu(d)g(frac{n}{d})} ]

blogs:

题目:

[HDU1695]GCD + [HAOI2011]Problem b + [POI2007]ZAP-Queries
~~三倍经验~~
[SDOI2015]约数个数和
[luogu1829]Crash的数字表格
[luogu2257]YY的GCD
[51nod]莫比乌斯函数之和
[BZOJ4805]欧拉函数求和
[SP4168]SQFREE - Square-free integers
[BZOJ2440][中山市选2011]完全平方数
[SDOI2014]数表（莫比乌斯反演+树状数组）
[luogu3768]简单的数学题
[BZOJ3309]DZY Loves Math
P4240 毒瘤之神的考验(真的毒瘤的预处理啊orz)
[NOI2016]循环之美
[SDOI2017]数字表格（关于幂的莫比乌斯反演orz）

二项式反演

[f(n)=sum_{k=p}^n (egin{matrix} n \ k end{matrix})g(k) ]

[g(n)=sum_{k=p}^n(-1)^{n-k}(egin{matrix} n \ k end{matrix})f(k) ]

莫比乌斯函数、二项式、斯特林数以及它们的反演

[BZOJ3622]已经没有什么好害怕的了

中国剩余定理

中国剩余定理与扩展 Lucas定理与扩展学习笔记

[codevs3990]中国余数定理 2

[egin{Bmatrix} x equiv c_1 (mod; m_1)\ x equiv c_2 (mod; m_2)\ cdots\ x equiv c_n (mod; m_n) end{Bmatrix} ]

其中((m_i, m_j)==1, i ot= j)
令(M=prod_{i=1}^nm_i)，
则(x=(sum_{i=1}^nc_i*frac{M}{m_i}*inv(frac{M}{m_i}, m_i))mod;M)

[POJ2891]Strange Way to Express Integers

[egin{Bmatrix} x equiv c_1 (mod; m_1)\ x equiv c_2 (mod; m_2)\ cdots\ x equiv c_n (mod; m_n) end{Bmatrix} ]

对于两个方程

[x equiv c_1 (mod; m_1)\ x equiv c_2 (mod; m_2)]

合并为一个，有解条件为((m_1, m_2)|(c_2-c_1))

[d=(m_1, m_2), m=frac{m_1m_2}{d}\ c=(inv(frac{m_1}{d}, frac{m_2}{d})*frac{c_2-c_1}{d})\% (frac{m_2}{d})*m_1+c_1]

最终(x=c\%m)

[luogu4720]【模板】扩展卢卡斯
求(C_n^m%p)
唯一分解(p=prod_{i=1}^qp_i^{k_i})

[egin{Bmatrix} x equiv C_n^m \%p_1^{k_1} (mod; p_1^{k_1})\ x equiv C_n^m \%p_2^{k_2} (mod; p_2^{k_2})\ cdots\ x equiv C_n^m \%p_q^{k_q} (mod; p_q^{k_q}) end{Bmatrix} ]

则(x)即为答案

公式:

[g(n)=sum_{d|n}f(d)$$ $$f(n)=sum_{d|n}{mu(d)g(frac{n}{d})} ]
[f(n)=sum_{k=p}^n (egin{matrix} n \ k end{matrix})g(k) ]

[g(n)=sum_{k=p}^n(-1)^{n-k}(egin{matrix} n \ k end{matrix})f(k) ]

[g(n)=sum_{n|d}{f(d)[d leq m]}$$ $$f(n)=sum_{n|d}{mu(frac{d}{n})g(d)[d leq m]} ]
如果(f(n))是积性函数，且((x, y) = 1)，则有$$f(xy)=f(x)f(y)$$
[sum_{i=1}^{n}{i[(i, n) == 1]}= frac{varphi(n)*n}2 ]

(用到结论:(if (i, n) == 1, then (n-i, n) = 1))
4. $$(id*mu)(i)=varphi(i)$$

[(varphi*I)(i)=id(i) ]

[(mu*I)(i)=e(i) ]

[[n == 1]=sum_{d|n}{mu(d)} ]
[n=sum_{d|n}{varphi(d)} ]
[sum_{i=1}^{n}{sum_{j=1}^{m}ij}=frac{n^2(n+1)^2}{4} ]
除数函数 $$sigma_k(n)=sum_{d|n}{d^k}$$
约数个数函数 $$ au(n)=sigma_0(n)=sum_{d|n}1$$
约数和函数$$sigma(n)=sigma_1(n)=sum_{d|n}d$$
[sum_{i=1}^ni=frac{n(n+1)}{2} ]

[sum_{i=1}^ni^2=frac{(n+1)(2n+1)n}{6} ]

[sum_{i=1}^ni^3=frac{n^2(n+1)^2}{4} ]

[varphi(ij)=frac{varphi(i)varphi(j)(i,j)}{varphi((i,j))} ]
[[f(x) == 1] = e(f(x))=(mu*I)(f(x))$$（常用于引进$mu$以进行莫比乌斯反演，如[NOI2016]循环之美） ]
[d(ij)=sum_{x|i}sum_{y|j}[gcd(x, y) == 1] ]
[]

x equiv c_1 (mod; m_1)
x equiv c_2 (mod; m_2)
cdots
x equiv c_n (mod; m_n)
end{Bmatrix}

[其中$(m_i, m_j)==1, i ot= j$ 令$M=prod_{i=1}^nm_i$，则$x=(sum_{i=1}^nc_i*frac{M}{m_i}*inv(frac{M}{m_i}, m_i))mod;M$ 15. ]

egin{Bmatrix}
x equiv c_1 (mod; m_1)
x equiv c_2 (mod; m_2)
cdots
x equiv c_n (mod; m_n)
end{Bmatrix}

[对于两个方程 $$x equiv c_1 (mod; m_1)\ x equiv c_2 (mod; m_2)]