初等数论笔记-算法竞赛相关-Ⅳ

字数统计: 2k | 阅读时长≈ 11 分钟

一些莫反入门题

Solution.

\begin{aligned} \sum_{i=1}^{a}\sum_{j=1}^{b}[gcd(i,j)==d]&=\sum_{i=1}^{\frac{a}{d}}\sum_{j=1}^{\frac{b}{d}}[gcd(i,j)==1]\\ &=\sum_{x=1}^{\lfloor\frac{a}{d}\rfloor} \sum_{y=1}^{\lfloor\frac{b}{d}\rfloor} \sum_{d|gcd(x,y)}\mu(d)\\ &=\sum_{d=1}^{min(\lfloor\frac{a}{d}\rfloor,\lfloor\frac{b}{d}\rfloor)}\sum_{x=1}^{\lfloor\frac{a}{d^2}\rfloor}\sum_{y=1}^{\lfloor\frac{b}{d^2}\rfloor}\mu(d)\\ &=\sum_{d=1}^{min(\lfloor\frac{a}{d}\rfloor,\lfloor\frac{b}{d}\rfloor)}\mu(d)\lfloor\frac{a}{d^2}\rfloor \lfloor\frac{b}{d^2}\rfloor \end{aligned}

对于给出的 n 个询问，每次求有多少个数对 $(x,y)$ ，满足 $a \le x \le b，c \le y \le d$ ，且 $\gcd(x,y) = k$ link

Solution.

思路同上，注意容斥。

Solution.

\begin{aligned} \sum_{k=1,\;k\in prime} ^{min(N,M)} \sum_{X=1}^N \sum_{y=1}^M[gcd(x,b)==k]&=\sum_{k=1,\;k\in prime} ^{min(N,M)} \sum_{x=1}^{\lfloor \frac{N}{k}\rfloor} \sum_{y=1}^{\lfloor \frac{M}{k}\rfloor} \sum_{d|gcd(x,y)} mu(d)\\ &=\sum_{k=1,\;k\in prime} ^{min(N,M)}\sum_{d=1}^{min(\lfloor \frac{N}{k}\rfloor,\lfloor \frac{M}{k}\rfloor)}\mu(d) \lfloor \frac{N}{k}\rfloor \lfloor \frac{M}{k}\rfloor\\ 令T=kd\\ &=\sum_{T=1}^{min(N,M)}\sum_{k|T,\;k\in prime} \mu(\frac{T}{k})\lfloor \frac{N}{k}\rfloor \lfloor \frac{M}{k}\rfloor\\ &=\sum_{T=1}^{min(N,M)}\lfloor \frac{N}{k}\rfloor \lfloor \frac{M}{k}\rfloor\sum_{k|T,\;k\in prime} \mu(\frac{T}{k})\\ \end{aligned}

\sum_{i=1}^n \sum_{j=1}^md(ij)

Solution.

对于 $d(ij)$ ，有

d(ij)=\sum_{x|i}\sum_{y|j}[gcd(i,j)==1]

即

\begin{aligned} \sum_{i=1}^n \sum_{j=1}^md(ij)&=\sum_{i=1}^n \sum_{j=1}^m\sum_{x|i}\sum_{y|j}[gcd(x,y)==1]\\ &=\sum_{i=1}^n \sum_{j=1}^m\sum_{x|i}\sum_{y|j}\epsilon (gcd(x,y))\\ &=\sum_{i=1}^n \sum_{j=1}^m\sum_{x|i}\sum_{y|j}\sum_{d|gcd(x,y)}\mu(d)\\ &=\sum_{i=1}^n \sum_{j=1}^m\sum_{x|i}\sum_{y|j} \sum_{d=1}^{min(n,m)}\mu(d)[d|gcd(x,y)]\\ &=\sum_{d=1}^{min(n,m)}\mu(d) \sum_{i=1}^n \sum_{j=1}^m\sum_{x|i}\sum_{y|j}[d|gcd(x,y)]\\ &=\sum_{d=1}^{min(n,m)}\mu(d) \sum_{i=1}^n \sum_{j=1}^m[d|gcd(x,y)]\lfloor\frac{n}{x}\rfloor \lfloor \frac{n}{y}\rfloor\\ &=\sum_{d=1}^{min(n,m)}\mu(d)\sum_{x=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{y=1}^{\lfloor\frac{m}{d}\rfloor}\lfloor\frac{n}{dx}\rfloor \lfloor \frac{n}{dy}\rfloor\\ &=\sum_{d=1}^{min(n,m)}\mu(d)\sum_{x=1}^{\lfloor\frac{n}{d}\rfloor}\lfloor\frac{n}{dx}\rfloor\sum_{y=1}^{\lfloor\frac{m}{d}\rfloor} \lfloor \frac{n}{dy}\rfloor \end{aligned}\\

Solution.

欧拉反演：

\begin{aligned} \sum_{i=1}^n\sum_{j=1}^n gcd(i,j)&=\sum_{i=1}^n\sum_{j=1}^n\sum_{d|gcd(i,j)}\phi(d)\\ &=\sum_{d=1}^n \phi(d) \lfloor\frac{n}{d}\rfloor^2 \end{aligned}

Solution.

经过映射可转换为对于序列 $a'_i,b'_i$ ，求满足 $a'_{x}=b'_{y}$ 且 $gcd(x,y)==1$ 的有序对数量

我们记 $f(n)=[gcd(x，y)==n]$ 的数量，再记 $F(n)=\sum_{n|N}f(N)$

那么由莫比乌斯倍数反演

f(n)=\sum_{n|N}F(N)\mu(N/n)

则

f(1)=\sum F(N)\mu(N)

即求

F(k)=\sum_{k|n}[gcd(x,y)==n]

杜教筛通常用低于线性的时间来解决一类积性函数的前缀和问题

\begin{aligned} &\quad \; \sum_{i=1}^n(f*g)(i)\\ &=\sum_{y=1}^n\sum_{x=1}^{\lfloor \frac{n}{y}\rfloor}f(x)g(y)\\ &=\sum_{y=1}^n g(y)\sum_{x=1}^{\lfloor \frac{n}{y}\rfloor}f(x)\\ &=\sum_{y=1}^n g(y) S(\lfloor n/y\rfloor)\\ &=g(1)S(n)+\sum_{y=2}^n g(y) S(\lfloor n/y\rfloor) \end{aligned}

得到

g(1)S(n)= \sum_{i=1}^n(f*g)(i)-\sum_{y=2}^n g(y) S(\lfloor n/y\rfloor)

在此基础上，如果用线性筛预处理出前 $n^{\frac23}$ 项的值，可优化到 $O(n^{\frac23})$

e.g.

筛 $\mu$ 的前缀和，注意到 $\mu*1=\epsilon$ ，令 $g=1$ ，则有

S(n)=\sum_{i=1}^n\epsilon(i)-\sum_{y=2}^nS(\lfloor n/y\rfloor)=1-\sum_{y=2}^nS(\lfloor n/y\rfloor)

筛 $\phi$ 的前缀和，注意到 $\phi*1=Id$ ，令 $g=1$ ，则有

S(n)=\frac{n(n+1)}{2}-\sum_{y=2}^nS(\lfloor n/y\rfloor)

打赏