Post 93

背影却，重叠回那少年。

[SCOI2016]萌萌哒

题目描述

一个长度为 $n$ 的大数，用 $S1S_2S_3 \cdots S_n$表示，其中 $S_i$ 表示数的第 $i$ 位, $S_1$ 是数的最高位。告诉你一些限制条件，每个条件表示为四个数，$l_1,r_1,l_2,r_2$，即两个长度相同的区间，表示子串$S{l1}S{l1+1}S{l1+2} \cdots S{r1}$与$S{l2}S{l2+1}S{l2+2} \cdots S{r_2}$完全相同。
比如 $n=6$ 时，某限制条件 $l_1=1,r_1=3,l_2=4,r_2=6$ ，那么 $123123$，$351351$ 均满足条件，但是 $12012$，$131141$ 不满足条件，前者数的长度不为 $6$ ，后者第二位与第五位不同。问满足以上所有条件的数有多少个。

输入输出格式

输入格式：
第一行两个数n和m，分别表示大数的长度，以及限制条件的个数。
接下来m行，对于第i行,有4个数 li1，ri1，li2，ri2，分别表示该限制条件对应的两个区间。
$1\le n\le 10^5$，$1\le m\le 10^5$ ，$ 1\le li1,ri1,li2,ri2 \le n $ ；并且保证 $ ri1-li1=ri2-li2 $ 。
输出格式：
一个数，表示满足所有条件且长度为n的大数的个数，答案可能很大，因此输出答案模 $ 10^9+7 $ 的结果即可。

输入输出样例

输入样例#1：
4 2
1 2 3 4
3 3 3 3

输出样例#1：
90

题解

身负重病依然想写题.jpg

结果根本想不出来还在硬想。

一个暴力的做法是直接用一个维护集合大小的并查集来暴力合并，合并完了把每个集合的大小记为$k_i$，答案就是$\sum 10^{k_i}$。时间复杂度$O(n^2)$

然后WA了，遂整起了WSL。

---

[SDOI2015]约数个数和

题目描述

$$\sum\limits_{i=1}^N\sum\limits_{j=1}^M d(ij)$$

数据范围：$1\leqslant N,M,T\leqslant 5\times 10^4$

首先给出一个公式：

$$d(ij)=\sum\limits_{x\mid i}\sum\limits_{y\mid j} [\gcd(x,y)=1]$$

因此所求为

$$\sum\limits_{i=1}^n\sum\limits_{j=1}^m\sum\limits_{x\mid i}\sum\limits_{y\mid j} [\gcd(x,y)=1]$$

改变求和顺序，先枚举因数 $x$ 和 $y$

$$\sum\limits_{x=1}^n\sum\limits_{y=1}^m \left\lfloor\frac{n}{x}\right\rfloor \left\lfloor\frac{m}{y}\right\rfloor [\gcd(x,y)=1]$$

将 $x,y$ 换成 $i,j$ 吧 QAQ

$$\sum\limits_{i=1}^n\sum\limits_{j=1}^m \left\lfloor\frac{n}{i}\right\rfloor \left\lfloor\frac{m}{j}\right\rfloor[\gcd(i,j)=1]$$

开始莫比乌斯反演！设

$$f(x)=\sum\limits_{i=1}^n\sum\limits_{j=1}^m \left\lfloor\frac{n}{i}\right\rfloor \left\lfloor\frac{m}{j}\right\rfloor[\gcd(i,j)=x]$$ $$g(x)=\sum_{x\mid d} f(d)$$

则有

$$g(x)=\sum\limits_{i=1}^n\sum\limits_{j=1}^m \left\lfloor\frac{n}{i}\right\rfloor \left\lfloor\frac{m}{j}\right\rfloor[x\mid\gcd(i,j)]$$

我们把 $x$ 提出就可以消除 $\gcd$ 的影响

$$g(x)=\sum\limits_{i=1}^{\frac{n}{x}}\sum\limits_{j=1}^{\frac{m}{x}} \left\lfloor\frac{n}{ix}\right\rfloor \left\lfloor\frac{m}{jx}\right\rfloor$$

再根据 $f(x)$ 的定义，得到答案为 $f(1)$
又因为

$$f(n)=\sum\limits_{n\mid d}\mu(\frac{d}{n})g(d)$$

故

$$f(1)=\sum\limits_{1\mid d}\mu(\frac{d}{1})g(d)=\sum_{i=1}^n \mu(i)g(i)$$

接下来再考虑如何求 $g(x)$，我们可以先计算 $s(x)=\sum\limits_{i=1}^{x} \left\lfloor\frac{x}{i}\right\rfloor$，就可以 $\Theta(1)$ 计算 $g(x)$。
时间复杂度：$\Theta(T\sqrt{n})$

Extended
如何证明 Solution 中的公式？

$$d(ij)=\sum\limits_{x\mid i}\sum\limits_{y\mid j} [\gcd(x,y)=1]$$

我们考虑把每个因子一一映射。
如果 $ij$ 的因子 $k$ 中有一个因子 $p^c$，$i$ 中有因子 $p^a$，$j$ 中有因子 $p^b$。我们规定：

如果 $c\leqslant a$，那么在 $i$ 中选择。
如果 $ca$，那么我们把 $c$ 减去 $a$，在 $j$ 中选择 $p^{c-a}$（在 $j$ 中选择 $p^e$ 表示的是 $p^{a+e}$）

对于 $ij$ 的因子 $k$ 的其他因子同理。于是对于任何一个 $k$ 有一个唯一的映射，且每一个选择对应着唯一的 $k$。
通过如上过程，我们发现：对于 $ij$ 的因子 $k=\prod {p_i}^{c_i}$，我们不可能同时在 $i$ 和 $j$ 中选择 $p_i$（优先在 $i$ 中选择，如果不够就只在 $j$ 中选择不够的指数），故 $x$ 和 $y$ 必须互质。
等式得证。

哈，真有趣，这是我学的Mobius inversion？

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

求解（对 $20101009$ 取模）

$$\sum\limits_{i=1}^n\sum\limits_{j=1}^m\operatorname{lcm}(i,j)$$

数据范围：$n,m\leqslant 10^7$

Solution

比天守阁的地板要简单。

易知原式等价于

$$\sum\limits_{i=1}^n\sum\limits_{j=1}^m\frac{i\cdot j}{\gcd(i,j)}$$

枚举最大公因数 $d$，显然两个数除以 $d$ 得到的数互质

$$\sum\limits_{i=1}^n\sum\limits_{j=1}^m\sum\limits_{d|i,d|j,\gcd(\frac{i}{d},\frac{j}{d})=1}\frac{i\cdot j}{d}$$

非常经典的 $\gcd$ 式子的化法

$$\sum\limits_{d=1}^n d\cdot\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{d}\rfloor}[\gcd(i,j)=1]\cdot i\cdot j$$

后半段式子中，出现了互质数对之积的和，为了让式子更简洁就把它拿出来单独计算。于是我们记

$$\operatorname{sum}(n,m)=\sum\limits_{i=1}^n\sum\limits_{j=1}^m [\gcd(i,j)=1]\cdot i\cdot j$$

接下来对 $\operatorname{sum}(n,m)$ 进行化简。首先枚举约数，并将 $[\gcd(i,j)=1]$ 表示为 $\varepsilon(\gcd(i,j))$

$$\sum\limits_{d=1}^n\sum\limits_{d|i}^n\sum\limits_{d|j}^m\mu(d)\cdot i\cdot j$$

设 $i=i’\cdot d$，$j=j’\cdot d$（其中 $i’,j’$ 指上式中的 $i,j$ ），显然式子可以变为

$$\sum\limits_{d=1}^n\mu(d)\cdot d^2\cdot\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{d}\rfloor}i\cdot j$$

观察上式，前半段可以预处理前缀和；后半段又是一个范围内数对之和，记

$$g(n,m)=\sum\limits_{i=1}^n\sum\limits_{j=1}^m i\cdot j=\frac{n\cdot(n+1)}{2}\times\frac{m\cdot(m+1)}{2}$$

可以 $\Theta(1)$ 求解
至此

$$\operatorname{sum}(n,m)=\sum\limits_{d=1}^n\mu(d)\cdot d^2\cdot g(\lfloor\frac{n}{d}\rfloor,\lfloor\frac{m}{d}\rfloor)$$

我们可以 $\lfloor\frac{n}{\lfloor\frac{n}{d}\rfloor}\rfloor$ 数论分块求解 $\operatorname{sum}(n,m)$ 函数。时间复杂度是$O(\sqrt{n})$
在求出 $\operatorname{sum}(n,m)$ 后，回到定义 $\operatorname{sum}$ 的地方，可得原式为

$$\sum\limits_{d=1}^n d\cdot\operatorname{sum}(\lfloor\frac{n}{d}\rfloor,\lfloor\frac{m}{d}\rfloor)$$

可见这又是一个可以数论分块求解的式子！
本题除了推式子比较复杂、代码细节较多之外，是一道很好的莫比乌斯反演练习题！（上述过程中，默认 $n\leqslant m$）
关于时间复杂度，这可真是难倒了数学不好的我

我们来分析一下。

如果最后的答案不使用根号优化，复杂度是

$O(\sum\limits_{i=1}^{n}\sqrt{\frac{n}{i}})$

然而这并不能算，但是我们把$\frac{n}{i}$的下取整去掉，求和换积分算子，那么放缩后求出来的复杂度

是$O(n)$（尽管听上去不科学，$\sum_{i=1}^{n} \frac{n}{i} = lnn + \gamma$)

验证：

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cmath>
int n;
int main()
{
	scanf("%d",&n);
	int ct = 0;
	for(int i = 1 ; i <= n ; i = n / (n / i) + 1)
		ct += std::sqrt(i);
	ct += std::sqrt(n);
	printf("%d\n",ct);
}

然后我求了一下1000000000，发现复杂度是14918223？？？

貌似不像线性。这个复杂度明显有误.

明天再搞。

来补坑。

直接考虑最终优化的复杂度怎么算。也就是$\sqrt{n/x}$对于每个取值只算一遍。

然后发现自己又想错了，最后一次来修改。

考虑到所求复杂度不会大于$2\int_{1}^{\sqrt{n}}\sqrt{x}~dx$

因此复杂度是$O(n^{\frac{3}{4}})$