CQOI 2015

刷题

---

Prob 1：[BZOJ 3930] 选数

给定$\ n, k, l, r\ $，询问：从$[l,r]$中选出$n$个数，使得$Gcd(a_1,a_2,\ldots,a_n) = k$的方案数

莫比乌斯反演

我们设
$\ f(x)\ $表示从$[l,r]$中选出$n$个数，使得$Gcd(a_1,a_2,\ldots,a_n) = k$的方案数
同时设
$g(x) = \sum_{x\mid d} f(d) = (\lfloor\frac{r}{x}\rfloor - \lfloor\frac{l - 1 }{x}\rfloor)^n$
$g(x)$是$f(x)$的倍数和，相当于是后缀和，而一般的莫比乌斯变换，是约数和，相当于前缀和
类比莫比乌斯反演的证明过程，我们容易证明：无论是约数和还是后缀和的莫比乌斯变换，都可以进行莫比乌斯反演

$$f(k) = \sum_{k\mid d}\mu(\frac{d}{k}) g(d)$$ $$= \sum_{j = 1}\mu(j)\cdot g(j\cdot k)$$ $$= \sum_{j = 1}^r\mu(j)\cdot (\lfloor\frac{r}{j\cdot k}\rfloor - \lfloor\frac{l - 1 }{j\cdot k}\rfloor)^n$$ 后面的那一坨分块搞，$\mu(x)$的前缀和怎么办？
题目的数据范围$10^9$……筛法会挂……
下面介绍一个比较神奇的$sum(x) = \sum_{i = 1}^N \mu(i)$的求法
$$sum(x) = 1 - \sum_{i = 2}^N sum(\lfloor\frac{N}{i}\rfloor)$$ 证明如下： $$sum(x) = \sum_{i = 1}^N \mu(i)$$ $$= 1 + \sum_{i = 2}^N \mu(i)$$ $$\because [i = 1] = \sum_{d\mid i} \mu(d) = \sum_{d\mid i,d\neq i} \mu(d) + \mu(i)$$ $$\therefore \mu(i) = [i = 1] - \sum_{d\mid i,d\neq i} \mu(d)$$ $$原式= 1 - \sum_{i = 2}^N \sum_{d\mid i,d\neq i} \mu(d)$$ $$= 1 - \sum_d \mu(d) \sum_{i = 2}^N [d\mid i\ \wedge\ d\neq i]$$ $$= 1 - \sum_d \mu(d) (\lfloor\frac{N}{d}\rfloor - 1)$$ $$= 1 - \sum_d \mu(d) \sum_{i = 2}^N [d \leq \lfloor\frac{N}{i}\rfloor]$$ $$= 1 - \sum_{i = 2}^N \sum_{d = 1}^{\lfloor\frac{N}{i}\rfloor} \mu(d)$$ $$= 1 - \sum_{i = 2}^N sum(\lfloor\frac{N}{i}\rfloor)$$ 这样一来，我们就可以来搞了
通过记忆化搜索，我们可以得到$\Theta(N^{\frac{3}{4}})$的算法

但是这样还不够
我们设定一个阈值，预处理出小于阈值的$sum$值
对于大于阈值的进行记忆化搜索
根据计算：

$$\Theta(N^{\frac{2}{3}}) + \sum_{i = 2}^{N^{\frac{1}{3}}}\Theta(\sqrt{\frac{N}{i}}) = \Theta(N^{\frac{2}{3}} + \int_2^{N^{\frac{1}{3}}}\sqrt{\frac{N}{x}}{\rm d}x) = \Theta(N^{\frac{2}{3}})$$ 所以，我们将阈值设置为$N^{\frac{2}{3}}$，也就是$10^6$
至此，问题完美解决。