莫反习题整理

如题。本文主要整理莫反习题的做法以及一些推式子技巧。

P2522 [HAOI2011] Problem b

题目让我们求

$$\sum_{i=a}^{b}\sum_{j=c}^{d}[\gcd(i,j)=k]$$

我们只需要会求

$$\sum_{i=1}^{x}\sum_{j=1}^{y}[\gcd(i,j)=k]$$

然后容斥一下就好了。

$$\begin{aligned} \sum_{i=1}^{x}\sum_{j=1}^{y}[\gcd(i,j)=k] & = \sum_{i=1}^{x/k}\sum_{j=1}^{y/k}[\gcd(i,j)=1] \\ & = \sum_{i=1}^{x/k}\sum_{j=1}^{y/k}\sum_{d|i,d|j}\mu(d) \\ & = \sum_{i=1}^{x/k}\sum_{j=1}^{y/k}\sum_{d}\mu(d)[d|i][d|j] & \cdots\cdots\text{①} \\ & = \sum_{d}\mu(d)\sum_{i=1}^{x/k}[d|i]\sum_{j=1}^{y/k}[d|j] \\ & = \sum_{d=1}^{\min\{\lfloor x/k\rfloor ,\lfloor y/k\rfloor \}}\mu(d)\left\lfloor\frac{x}{kd}\right\rfloor\left\lfloor\frac{y}{kd}\right\rfloor \end{aligned}$$

技巧：在不会跳步的时候，建议使用 ① 处方法，使用艾弗森括号代替 $\sum$ 下的条件进行求和顺序的交换。

P3455 [POI2007] ZAP-Queries

同 P2522。

P2257 YY的GCD

$$\begin{aligned} \sum_{i=1}^{n}\sum_{j=1}^{m}[\gcd(i,j)\text{ is prime}] & = \sum_{p\text{ is prime}}\sum_{i=1}^{n}\sum_{j=1}^{m}[\gcd(i,j)=p] \\ & = \sum_{p\text{ is prime}}\sum_{i=1}^{n/p}\sum_{j=1}^{m/p}[\gcd(i,j)=1] \\ & = \sum_{p\text{ is prime}}\sum_{i=1}^{n/p}\sum_{j=1}^{m/p}\sum_{d|i,d|j}\mu(d) \\ & = \sum_{p\text{ is prime}}\sum_{d}\mu(d)\left\lfloor\frac{n}{dp}\right\rfloor\left\lfloor\frac{m}{dp}\right\rfloor \\ & = \sum_{q}\left\lfloor\frac{n}{q}\right\rfloor\left\lfloor\frac{m}{q}\right\rfloor\sum_{p|q,p\text{ is prime}}\mu(\frac{q}{p}) & \cdots\cdots\text{①} \end{aligned}$$

观察到

$$f(x) = \sum_{p|x,p\text{ is prime}}\mu(\frac{x}{p}) \\$$

是积性函数。对其进行线性筛然后整除分块处理原式即可。

技巧： ① 处，考虑到下取整除法的分母是 $dp$，于是令 $q=dp$ 转而枚举 $q$，便于进行整除分块。

SP5971 LCMSUM - LCM Sum

$$\begin{aligned} \sum_{i=1}^{n}\operatorname{lcm}(i,n) & = n\sum_{i=1}^{n}\frac{i}{\gcd(i,n)} \\ & = n\sum_{d|n}\frac{1}{d}\sum_{i=1}^{n}i[\gcd(i,n)=d] \\ & = n\sum_{d|n}\frac{1}{d}\sum_{i=1}^{n/d}id[\gcd(i,\frac{n}{d})=1] \\ & = n\sum_{d|n}\sum_{i=1}^{n/d}i\sum_{k|i,k|\frac{n}{d}}\mu(k) \\ & = n\sum_{d|n}\sum_{i=1}^{n/d}i\sum_k[k|i][dk|n]\mu(k) \\ & = n\sum_{d|n}\sum_{k|\frac{n}{d}}k\mu(k)\sum_{i=1}^{n/kd}i \\ \text{令 }f(x) & = \frac{x(x+1)}{2},\text{ 则} \\ \text{原式} & = n\sum_{d|n}\sum_{k|\frac{n}{d}}k\mu(k)f(\frac{n}{kd}) \\ & = n\sum_{q|n}f(\frac{n}{q})\sum_{k|q}k\mu(k) \\ \text{令 }g(x) & = \sum_{k|x}k\mu(k),\text{ 则} \\ \text{原式} & = n\sum_{q|n}g(q)f(\frac{n}{q}) \end{aligned}$$

观察到 $g$ 是积性函数，线性筛出它。

答案是卷积形式，用类似埃氏筛的方法预处理出它。

P1829 [国家集训队] Crash 的数字表格 / JZPTAB

不妨设 $n\le m$。

令 $S(x)=\frac{x(x+1)}{2}$。

$$\begin{aligned} \sum_{i=1}^{n}\sum_{j=1}^{m}\operatorname{lcm}(i,j) & = \sum_{i=1}^{n}\sum_{j=1}^{m}\frac{ij}{\gcd(i,j)} \\ & = \sum_{d=1}^{n}\frac{1}{d}\sum_{i=1}^{n}\sum_{j=1}^{m}ij[\gcd(i,j)=d] \\ & = \sum_{d=1}^{n}d\sum_{i=1}^{n/d}\sum_{j=1}^{m/d}ij[\gcd(i,j)=1] \\ & = \sum_{d=1}^{n}d\sum_{i=1}^{n/d}\sum_{j=1}^{m/d}ij\sum_{k|i,k|j}\mu(k) \\ & = \sum_{d=1}^{n}d\sum_{k=1}^{n/d}k^2\mu(k)\sum_{i=1}^{\frac{n}{dk}}i\sum_{j=1}^{\frac{m}{dk}}j \\ & = \sum_{d=1}^{n}d\sum_{k=1}^{n/d}k^2\mu(k)S(\left\lfloor\frac{n}{dk}\right\rfloor)S(\left\lfloor\frac{m}{dk}\right\rfloor) \\ & = \sum_{g=1}^{n}gS(\left\lfloor\frac{n}{g}\right\rfloor)S(\left\lfloor\frac{m}{g}\right\rfloor)\sum_{k|g}k\mu(k) \end{aligned}$$

因为

$$f(x)=\sum_{k|x}k\mu(k)$$

是积性函数，我们线性筛出它即可。

P3327 [SDOI2015]约数个数和

不妨设 $n\le m$。

$$\begin{aligned} \sum_{i=1}^{n}\sum_{j=1}^{m}d(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\sum_y[x|i][y|j][\gcd(x,y)=1] \\ & = \sum_{x=1}^{n}\sum_{y=1}^{m}[gcd(x,y)=1]\left\lfloor\frac{n}{x}\right\rfloor\left\lfloor\frac{m}{y}\right\rfloor \\ & = \sum_{x=1}^{n}\sum_{y=1}^{m}\sum_{d|x,d|y}\mu(d)\left\lfloor\frac{n}{x}\right\rfloor\left\lfloor\frac{m}{y}\right\rfloor \\ & = \sum_{d}\mu(d)\sum_{x=1}^{n/d}\sum_{y=1}^{m/d}\left\lfloor\frac{n}{dx}\right\rfloor\left\lfloor\frac{m}{dy}\right\rfloor \\ & = \sum_{d=1}^{n}\mu(d)\sum_{x=1}^{n/d}\left\lfloor\frac{n}{dx}\right\rfloor\sum_{y=1}^{m/d}\left\lfloor\frac{m}{dy}\right\rfloor \end{aligned}$$

使用整除分块预处理

$$f(x)=\sum_{i=1}^{x}\left\lfloor\frac{x}{i}\right\rfloor$$

因此，

$$\begin{aligned} \sum_{i=1}^{n}\sum_{j=1}^{m}d(ij) & = \sum_{d=1}^{n}\mu(d)\sum_{x=1}^{n/d}\left\lfloor\frac{n}{dx}\right\rfloor\sum_{y=1}^{m/d}\left\lfloor\frac{m}{dy}\right\rfloor \\ & = \sum_{d=1}^{n}\mu(d)f(\left\lfloor\frac{n}{d}\right\rfloor)f(\left\lfloor\frac{m}{d}\right\rfloor) \end{aligned}$$

整除分块处理每个询问即可。

P3312 [SDOI2014]数表

先不考虑 $\le a$ 的限制条件。

设 $f(d)$ 表示 $d$ 的约数和。

不妨设 $n\le m$。

$$\begin{aligned} \sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{d|i,d|j}d & = \sum_{d=1}^{n}f(d)\sum_{i=1}^{n/d}\sum_{j=1}^{m/d}[\gcd(i,j)=1] \\ & = \sum_{d=1}^{n}f(d)\sum_{i=1}^{n/d}\sum_{j=1}^{m/d}\sum_{k|i,k|j}\mu(k) \\ & = \sum_{d=1}^{n}f(d)\sum_{k=1}^{n}\mu(k)\left\lfloor\frac{n}{dk}\right\rfloor\left\lfloor\frac{m}{dk}\right\rfloor \\ & = \sum_{q=1}^{n}\left\lfloor\frac{n}{q}\right\rfloor\left\lfloor\frac{m}{q}\right\rfloor\sum_{d|q}f(d)\mu\left(\frac{q}{d}\right) \end{aligned}$$

令

$$g(x)=\sum_{d|x}f(d)\mu\left(\frac{x}{d}\right)$$

对于每个询问，只有 $\le a$ 的 $f(d)$ 才会被统计到。

那么，我们预处理出所有的 $f(x)$ 并进行排序，然后将询问离线按 $a$ 排序。

每次 $a$ 增加的时候，对影响到的 $g(x)$ 累加贡献。

我们需要快速单点修改 $g(x)$，并快速得到 $g(x)$ 的前缀和。

使用树状数组维护 $g(x)$ 即可。

P4449 于神之怒加强版

不妨设 $n\le m$。

$$\begin{aligned} \sum_{i=1}^{n}\sum_{j=1}^{m}\gcd(i,j)^k & = \sum_{d}d^k\sum_{i=1}^{n}\sum_{j=1}^{m}[\gcd(i,j)=d] \\ & = \sum_{d}d^k\sum_{i=1}^{n/d}\sum_{j=1}^{m/d}[\gcd(i,j)=1] \\ & = \sum_{d}d^k\sum_{i=1}^{n/d}\sum_{j=1}^{m/d}\sum_{g|i,g|j}\mu(g) \\ & = \sum_{d=1}^{n}d^k\sum_{g=1}^{n/d}\mu(g)\left\lfloor\frac{n}{dg}\right\rfloor\left\lfloor\frac{m}{dg}\right\rfloor \\ & = \sum_{h=1}^{n}\left\lfloor\frac{n}{h}\right\rfloor\left\lfloor\frac{m}{h}\right\rfloor\sum_{d|h}d^k\mu\left(\frac{h}{d}\right) \end{aligned}$$

观察到

$$f(x)=\sum_{d|x}d^k\mu\left(\frac{x}{d}\right)$$

是积性函数。于是我们用线性筛、快速幂预处理出它。然后整除分块处理每个询问即可。

P3768 简单的数学题

$$\begin{aligned} \sum_{i=1}^{n}\sum_{j=1}^{n}ij\gcd(i,j) & = \sum_{d}d\sum_{i=1}^{n}\sum_{j=1}^{n}ij[\gcd(i,j)=d] \\ & = \sum_{d}d^3\sum_{i=1}^{n/d}\sum_{j=1}^{n/d}ij[gcd(i,j)=1] \\ & = \sum_{d}d^3\sum_{i=1}^{n/d}\sum_{j=1}^{n/d}ij\sum_{g|i,g|j}\mu(g) \\ & = \sum_{d=1}^{n}d^3\sum_{g}g^2\mu(g)\sum_{i=1}^{n/dg}i\sum_{j=1}^{n/dg}j \end{aligned}$$

记 $S(x)=\sum_{i=1}^{x}i\sum_{j=1}^{x}j = \frac{x^2(x+1)^2}{4}$。

$$\begin{aligned} \sum_{d=1}^{n}d^3\sum_{g}g^2\mu(g)\sum_{i=1}^{n/dg}i\sum_{j=1}^{n/dg}j & = \sum_{d=1}^{n}d^3\sum_{g}g^2\mu(g)S(\left\lfloor\frac{n}{dg}\right\rfloor) \\ & = \sum_{k=1}^{n}S(\left\lfloor\frac{n}{k}\right\rfloor)\sum_{d|k}d^3\left(\frac{k}{d}\right)^2\mu\left(\frac{k}{d}\right) \\ & = \sum_{k=1}^{n} k^2 S(\left\lfloor\frac{n}{k}\right\rfloor)\sum_{d|k}d\mu\left(\frac{k}{d}\right) \\ & = \sum_{k=1}^{n} k^2 S(\left\lfloor\frac{n}{k}\right\rfloor) \varphi(k) \end{aligned}$$

注意到

$$f(x)=x^2\varphi(x)$$

是积性函数。

观察数据范围，线性筛 $f$ 不行，需要杜教筛。

---

对于杜教筛：令 $f(x)=x^2\varphi(x)$，$s(x)=\sum_{i=1}^{x}f(x)$

$$\begin{aligned} \sum_{i=1}^n (f*g)(i) & = \sum_{i=1}^{n}\sum_{d|i} g(d)f(i/d) \\ & = \sum_{d=1}^{n} g(d)\sum_{i=1}^{n/d}f(i)\\ & = \sum_{d=1}^{n} g(d)s(n/d) \\ \therefore s(n)g(1) & = \sum_{i=1}^{n}(f*g)(i)-\sum_{d=2}^{n}g(d)s(n/d)\\ \end{aligned}$$

令 $g(x)=x^2$，则

$$\begin{aligned} (f*g)(x) & = \sum_{d|x}f(d)g(x/d)\\ & = x^2\sum_{d|x}\varphi(d) \\ & = x^3 \\ \therefore \sum_{i=1}^{x}(f*g)(i)&=\frac{x^2(x+1)^2}{4} \end{aligned}$$

P3704 [SDOI2017]数字表格

不妨设 $n\le m$。

$$\begin{aligned} \prod_{i=1}^{n}\prod_{j=1}^{m}f_{\gcd(i,j)} & = \prod_{d}f_d^{\sum_{i=1}^{n}\sum_{j=1}^{m}[\gcd(i,j)=d]} \\ & = \prod_{d=1}^{n}f_{d}^{\sum_{i=1}^{n/d}\sum_{j=1}^{m/d}[\gcd(i,j)=1]} \\ \sum_{i=1}^{n/d}\sum_{j=1}^{m/d}[\gcd(i,j)=1] & = \sum_{i=1}^{n/d}\sum_{j=1}^{m/d}\sum_{g|i,g|j}\mu(g) \\ & = \sum_{g=1}^{n/d}\mu(g)\left\lfloor\frac{n}{gd}\right\rfloor\left\lfloor\frac{m}{gd}\right\rfloor \\ \therefore \prod_{i=1}^{n}\prod_{j=1}^{m}f_{\gcd(i,j)} & = \prod_{d=1}^{n}f_d^{\sum_{g=1}^{n/d}\mu(g)\left\lfloor\frac{n}{gd}\right\rfloor\left\lfloor\frac{m}{gd}\right\rfloor} \\ & = \prod_{k=1}^{n}\prod_{d|k}f_d^{\left\lfloor\frac{n}{k}\right\rfloor\left\lfloor\frac{m}{k}\right\rfloor\mu(\left\lfloor\frac{k}{d}\right\rfloor)} \\ & = \prod_{k=1}^{n}\left(\prod_{d|k}f_d^{\mu(\left\lfloor\frac{k}{d}\right\rfloor)}\right)^{\left\lfloor\frac{n}{k}\right\rfloor\left\lfloor\frac{m}{k}\right\rfloor} \end{aligned}$$

用类似埃氏筛的方法预处理

$$g(x)=\prod_{d|x}f_d^{\mu(\left\lfloor\frac{x}{d}\right\rfloor)}$$

即可。询问用整除分块。

注意对指数 $\left\lfloor\frac{n}{k}\right\rfloor\left\lfloor\frac{m}{k}\right\rfloor$ 取模时使用费马小定理 $a^{p-1}\equiv 1\ (\bmod\ p)$。