min_25筛

## 前置知识

1.乘性函数

$$f(nm)=f(n)·f(m)$$

$$f(nm)=f(n)·f(m)$$

2.一些常用的乘性函数

$$I(n)=1$$

$$\epsilon(n)=[n=1]$$

$$id^k(n)=n^k$$

$$d(n)=\sum_{i=1}^n[n \space mod \space i=0]$$

$$\sigma_k(n)=\sum_{i=1}^n i^k[n \space mod \space i=0]$$

$$\varphi(n)=\sum_{i=1}^n [gcd(i,n)=1]$$

$$\mu(n)$$

3.狄利克雷卷积

$$h(n)=f(n)*g(n)=\sum_{d|n}f(d)g(\lfloor \frac{n}{d}\rfloor)$$

3.1一些常用的卷积

$$f*\epsilon=f$$

$$I*\mu=\epsilon$$

$$id*\mu=\varphi$$

$$\varphi*I=id$$

$$id*\mu=\varphi$$

## 莫比乌斯反演

1.定义

$$F=f*I$$

$$f=F*\mu$$

2.证明

$$F*\mu=(f*I)*mu$$

$$=f*(I*\mu)$$

$$=f*\epsilon=f$$

3.某些常用套路

$$[n=1]=\sum_{d|n}\mu(d)$$

$$n=\sum_{d|n}\varphi(d)$$

$$\sum_{k=1,k \space is \space prime}^n\sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)=d](n>=m)$$

$$=\sum_{k=1,k \space is \space prime}^n\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{i=1}^{\lfloor\frac{m}{k}\rfloor}[gcd(i,j)=1]$$ $$=\sum_{k=1,k \space is \space prime}^n\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{i=1}^{\lfloor\frac{m}{k}\rfloor}\sum_{d|gcd(i,j)}\mu(d)$$ $$=\sum_{k=1,k \space is \space prime}^n \sum_{d=1}^{\lfloor\frac{n}{k}\rfloor}\mu(d)\lfloor\frac{n}{kd}\rfloor\lfloor\frac{m}{kd}\rfloor$$

$$=\sum_{k=1,k \space is \space prime}^n \sum_{d=1}^{\lfloor\frac{n}{k}\rfloor}\mu(\frac{T}{k})\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor$$

$$=\sum_{T=1}^n\lfloor \frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor\sum_{k|T,k\space is \space prime}\mu(\frac{T}{k})$$

$$\sum_{i=1}^{n}\sum_{j=1}^{m}ij·gcd(i,j)\space mod \space p$$

$$\sum_{i=1}^{n}\sum_{j=1}^{n}ij·gcd(i,j)$$

$$=\sum_{d=1}^{n}d\sum_{i=1}^{n}\sum_{j=1}^{n}ij[gcd(i,j)=d]$$

$$=\sum_{d=1}^{n}d^3\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}ij[gcd(i,j)=1]$$

$$=\sum_{d=1}^{n}d^3\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}ij\sum_{k|gcd(i,j)}\mu(k)$$

$$=\sum_{d=1}^{n}d^3\sum_{k=1}^{\lfloor\frac{n}{d}\rfloor}\mu(k)k^2\sum_{i=1}^{\lfloor\frac{n}{kd}\rfloor}\sum_{i=1}^{\lfloor\frac{n}{kd}\rfloor}ij$$

$$=\sum_{d=1}^{n}d^3\sum_{k=1}^{\lfloor\frac{n}{d}\rfloor}\mu(k)k^2(\frac{\lfloor\frac{n}{kd}\rfloor(\lfloor\frac{n}{kd}\rfloor+1)}{2})^2$$

$$=\sum_{d=1}^{n}d^3\sum_{k=1}^{\lfloor\frac{n}{d}\rfloor}\mu(k)k^2s^2(\lfloor\frac{n}{kd}\rfloor)$$

$$=\sum_{d=1}^{n}d\sum_{k=1}^{\lfloor\frac{n}{d}\rfloor}\mu(\frac{T}{d})T^2s^2(\lfloor\frac{n}{T}\rfloor)$$

$$=\sum_{T=1}^{n}T^2s^2(\lfloor\frac{n}{T}\rfloor)\sum_{d|T}\mu(\frac{T}{d})d$$

$$=\sum_{T=1}^{n}T^2s^2(\lfloor\frac{n}{T}\rfloor)\sum_{d|T}\mu(\frac{T}{d})id(d)$$

$$=\sum_{T=1}^{n}T^2s^2(\lfloor\frac{n}{T}\rfloor)\varphi(T)$$

$$n=\sum_{d|n}\varphi(d)$$

$$\sum_{i=1}^{n}\sum_{j=1}^{n}ij·gcd(i,j)$$

$$=\sum_{i=1}^{n}\sum_{j=1}^{n}ij\sum_{d|gcd(i,j)}\varphi(d)$$

$$=\sum_{d=1}^{n}\varphi(d)\sum_{d|i}\sum_{d|j}ij$$

$$=\sum_{d=1}^{n}\varphi(d)d^2\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}ij$$

$$=\sum_{d=1}^{n}\varphi(d)d^2s^2(\lfloor\frac{n}{d}\rfloor)$$

## 杜教筛

$$\sum_{i=1}^n h(i)=\sum_{i=1}^{n}\sum_{d|i}f(d)g(\lfloor\frac{i}{d}\rfloor)$$

$$=\sum_{d=1}^n g(d)·\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}f(i)$$

$$=\sum_{d=1}^n g(d)·s(\lfloor\frac{n}{d}\rfloor)$$

$$\sum_{i=1}^n h(i)=g(1)·s(n)+\sum_{d=2}^n g(d)·s(\lfloor\frac{n}{d}\rfloor)$$

$$g(1)·s(n)=\sum_{i=1}^n h(i)-\sum_{d=2}^n g(d)·s(\lfloor\frac{n}{d}\rfloor)$$

h可以通过前缀和求，而后半段对g求前缀和，s可以进行数论分块

$$s(n)=\sum_{i=1}^{n}\mu(i)$$

$$s(n)=1-\sum_{d=2}^{n}s(\lfloor\frac{n}{d}\rfloor)$$

$$s(n)=\sum_{i=1}^{n}\varphi(i)$$

$$s(n)=\sum_{i=1}^{n}id(i)-\sum_{d=2}^ns(\lfloor\frac{n}{d}\rfloor)$$

$$=\frac{n(n+1)}{2}-\sum_{d=2}^ns(\lfloor\frac{n}{d}\rfloor)$$

$$s(n)=\sum_{i=1}^{n}\varphi(i)i$$

$$(f*g)(n)=\sum_{d|n}\varphi(d)·d·(\frac{n}{d})$$

$$=\sum_{d|n}\varphi(d)n$$

$$=n^2$$

$$s(n)=\sum_{i=1}^ni^2-\sum_{i=2}^ns(\lfloor\frac{n}{d}\rfloor)·i$$

$$s(n)=\frac{n(n+1)(2n+1)}{6}-\sum_{i=2}^ns(\lfloor\frac{n}{d}\rfloor)·i$$

## min_25筛

$$\sum_{i=1}^{n}F(i)$$

$$\sum_{i=2}^{n}f(i)$$

$$g(n,j)=g(n,j-1)\space\space(P_j^2>n)$$

$$g(n,j)=g(n,j-1)-f(P_j)·g(\frac{n}{P_j},j-1)$$

$$g(n,j)=g(n,j-1)-f(P_j)·(g(\frac{n}{P_j},j-1)-g(P_j-1,j-1))\space\space(P_j^2<=n)$$

$$S(n,j)=\sum_{i=2}^nF(i),min(p_i)>=P_j$$

$$g(n,|P|)-g(P_j-1,j-1)$$

$$\sum_{i=j}^{P_i^2<=n}\sum_{k=1}^{P_i^{k+1}<=n}(F(P_{i}^k)S(\frac{n}{P_i^k},i+1)+F(P_i^{k+1}))$$

$$S(n,j)=g(n,|P|)-g(P_j-1,j-1)+\sum_{i=j}^{P_i^2<=n}\sum_{k=1}^{P_i^{k+1}<=n}(F(P_{i}^k)S(\frac{n}{P_i^k},i+1)+F(P_i^{k+1}))$$

$$\sum_{i=1}^nF(i)=S(n,1)+f(1)$$

$g$ 函数可以通过递归或者递推求出， $S$ 函数可以递归求出