标签：lfloor GPHP limits dfrac sum 枚举 Vol.1 Math

GPHP Vol.1 Math

Introduction: 本计划将记录杂题，采用循序渐进的方法，先给出 Hint，然后给出 Solution，力求还原思维过程。记录什么题随缘。

这是 GPHP 第一期。每期计划 4-5 个题目。

Table of Content

1. <luogu> P3312 [SDOI2014] 数表

P3312 [SDOI2014] 数表

P3312 [SDOI2014] 数表 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

标签

莫比乌斯反演，前缀和，数据结构，最大公约数

Hints

Hint1

注意到如果不考虑限制就是求 $\sum_{i=1}^n\sum_{j=1}^m \sigma_1(\gcd(i,j))$

Hint2

枚举 gcd 以进行化简（经典套路）

Hint3

你应该得到了 $$\sum\limits_{T=1}^n\lfloor\dfrac{n}{T}\rfloor\lfloor\dfrac{m}{T}\rfloor\sum\limits_{d|T}\sigma_1(d)\mu(\dfrac{T}{d})$$ 观察它，发现后面这一部分非常独立 有很多次询问，但是并不意味着每次都必须重新计算后面的部分。 那么对于不同的 a，为了避免重复计算后面的部分，你知道应该怎么做了吗？

Hint4

转换视角，要避免反复计算，最重要的就是不能枚举约数，而是枚举倍数。 考虑动态维护后面这个式子。我们必须保证每个数只被枚举一次倍数。

Hint5

请把询问从小到大，按 a 排序。然后动态维护，并做整除分块。

你想到了百分之几呢？

Solution

先不考虑 \(a\) 的限制，那么要求的即：

\[\sum_{i=1}^n\sum_{j=1}^m \sigma_1(\gcd(i,j)) \]

处理套在函数里面的 \(\gcd\) 常用的方法是枚举他，并使用反演结论得到：

\[\sum\limits_{T=1}^n\lfloor\dfrac{n}{T}\rfloor\lfloor\dfrac{m}{T}\rfloor\sum\limits_{d|T}\sigma_1(d)\mu(\dfrac{T}{d}) \]

考虑 \(a\) 的限制，注意到后面的部分比较隔离，所以就避免重复计算，每次枚举 \(d\) 的倍数动态更新，考虑到调和级数的限制，复杂度为 \(n\ln n\) 级别，由于整除分块的时候要用到后面那个函数的前缀和，故最后为一个单点修改区间查询的问题，可以使用树状数组解决。

Trick \(\mu * 1=[n=1]\) 、动态维护的思路、枚举因数转枚举倍数

标签：lfloor,GPHP,limits,dfrac,sum,枚举,Vol.1,Math
From： https://www.cnblogs.com/haozexu/p/18361007