好无聊啊，来总结一下这几天学习的东西。
整除分块
整除分块常用于求解以下形式的式子：
\(\sum\limits_{i=1}\limits^{n} f(i)g(\lfloor \dfrac{n}{i} \rfloor)\)
其中 \(f\) 函数前缀和易得。
直接写结论：
\(\lfloor \dfrac{n}{i} \rfloor\) 最多只有 \(\sqrt{n}\) 种取值并且连续。我们将连续相同的一个取值段称为一个块，那么 \(x\) 所在块的右端点为 \(\lfloor \dfrac{n}{\lfloor \frac{n}{x} \rfloor} \rfloor\)。
那么我们可以利用这个性质解决问题：
例题1 UVA11526 H(n)
求 \(\sum\limits_{i=1}\limits^{n} \lfloor \dfrac{n}{i} \rfloor\)。
模板题。\(f,g\) 函数均为 \(id\) 函数。显然前缀和易求，那么就可以使用整除分块。
while(now<=n){
res+=(n/(n/now)-now+1)*(n/now);
now=n/(n/now)+1;
}
例题 2 P2261 [CQOI2007] 余数求和
给定 \(n,k\)，求 \(\sum\limits_{i=1}\limits^{n} k \bmod i\)。
尽人皆知，原式 \(= \sum\limits_{i=1}\limits^{n} k - k \times \lfloor \dfrac{k}{i} \rfloor\)。
又出现了那个整除式子，可以使用整除分块了。
while(now<=n){
int r=(k/now)?(k/(k/now)):n;
r=min(r,n),res+=(F(now,r))*(k/now);
now=r+1;
}
cout<<n*k-res<<endl;
其实，整除分块更多是用于莫比乌斯反演的一个优化求和。
狄利克雷卷积
我们定义两个积性函数 \(f,g\) 的狄利克雷卷积 \((f * g)(n) = \sum\limits_{d|n} f(d)g(\dfrac{n}{d})\)。
狄利克雷卷积满足以下性质：
-
交换律：\(f * g = g * f\)；
-
结合律：\(f * (g * h) = (f * g) * h\)；
-
分配律：\((f + g) * h = f * h + g * h\)。
同时满足以下几条：
-
\(\mu * 1 = \epsilon\)
-
\(\varphi * 1 = id\)
-
\(f * \epsilon = f\)
-
\(\mu * id = \varphi\)
这些性质会经常用到。
和式变换
这块内容很重要，是做题推式子的基础。
和式变换定律
-
分配律：\(\sum k a_i = k \sum a_i\)；
-
交换律：\(\sum a_i = \sum a_{b_i}\)，其中 \(b\) 是 \(1 \sim n\) 的一个排列；
-
结合律：\(\sum (a_i + b_i) = \sum a_i + \sum b_i\)。
和式变换技巧
-
替换条件式：\(\sum\limits_{d | \gcd(n,m)} d = \sum\limits_{d=1}\limits^n [d|i][d|j]d\)
-
替换指标变量：\(\sum\limits_{i=1}\limits^{n} \sum\limits_{j=1}\limits^{m} [\gcd(i,j) = k] = \sum\limits_{ik=1}\limits^{n} \sum\limits_{jk=1}\limits^{m} [\gcd(i,j)=k] = \sum\limits_{i=1}\limits^{\lfloor \frac{n}{k} \rfloor} \sum\limits_{j=1}\limits^{\lfloor \frac{m}{k} \rfloor} [\gcd(i,j)=1]\)
-
交换求和顺序：\(\sum\limits_{i=1}\limits^{n} \sum\limits_{j=1}\limits^{m} f(i)g(j) = \sum\limits_{j=1}\limits^{m} \sum\limits_{i=1}\limits^{n} f(i)g(j)\)
-
分离变量（各回各家，各找各妈）：\(\sum\limits_{i=1}\limits^{n} \sum\limits_{j=1}\limits^{m} f(i)g(j) = \sum\limits_{i=1}\limits^{n} f(i) \sum\limits_{j=1}\limits^{m} g(j)\)
熟悉上述变换以后，就可以做题了！
先上一个被清峥称为板子的题：
例题 1 P3455 [POI2007] ZAP-Queries
给定 \(n,m,k\)，求 \(\sum\limits_{i=1}\limits^{n} \sum\limits_{j=1}\limits^{m} [\gcd(i,j)=k]\)。
替换指标变量：
\[\sum\limits_{i=1}\limits^{n} \sum\limits_{j=1}\limits^{m} [\gcd(i,j)=k] \]\[=\sum\limits_{ik=1}\limits^{n} \sum\limits_{jk=1}\limits^{m} [\gcd(i,j)=k] \]\[= \sum\limits_{i=1}\limits^{\lfloor \frac{n}{k} \rfloor} \sum\limits_{j=1}\limits^{\lfloor \frac{m}{k} \rfloor} [\gcd(i,j)=1] \]因为我们有 \(\mu * 1 = \epsilon\)，所以我们有：
\[\sum\limits_{i=1}\limits^{\lfloor \frac{n}{k} \rfloor} \sum\limits_{j=1}\limits^{\lfloor \frac{m}{k} \rfloor} [\gcd(i,j)=1] \]\[= \sum\limits_{i=1}\limits^{\lfloor \frac{n}{k} \rfloor} \sum\limits_{j=1}\limits^{\lfloor \frac{m}{k} \rfloor} \sum\limits_{d|\gcd(i,j)} \mu(d) \]枚举 \(\gcd\)：
\[= \sum\limits_{i=1}\limits^{\lfloor \frac{n}{k} \rfloor} \sum\limits_{j=1}\limits^{\lfloor \frac{m}{k} \rfloor} \sum\limits_{d=1}\limits^{\lfloor \frac{n}{k} \rfloor} [d = \gcd(i,j)]\mu(d) \]\[= \sum\limits_{i=1}\limits^{\lfloor \frac{n}{k} \rfloor} \sum\limits_{j=1}\limits^{\lfloor \frac{m}{k} \rfloor} \sum\limits_{d=1}\limits^{\lfloor \frac{n}{k} \rfloor} [d|i][d|j]\mu(d) \]其实就是替换条件式。
分离变量：
\[= \sum\limits_{d=1}\limits^{\lfloor \frac{n}{k} \rfloor} \mu(d) \sum\limits_{i=1}\limits^{\lfloor \frac{n}{k} \rfloor} [d|i] \sum\limits_{j=1}\limits^{\lfloor \frac{m}{k} \rfloor} [d|j] \]显然：
\[= \sum\limits_{d=1}\limits^{\lfloor \frac{n}{k} \rfloor} \mu(d) \lfloor \dfrac{n}{dk} \rfloor \lfloor \dfrac{m}{dk} \rfloor \]至此推式子已经完成，观察到后面的 \(\lfloor \dfrac{n}{dk} \rfloor \lfloor \dfrac{m}{dk} \rfloor\) 完全可以整除分块处理，而 \(\mu(d)\) 的前缀和通过筛法易求，于是本题就做完了，时间复杂度 \(O(\sqrt n)\)。
n/=k,m/=k;
while(now<=min(n,m)){
int r=min(n/(n/now),m/(m/now));
res+=(sum[r]-sum[now-1])*(n/now)*(m/now),now=r+1;
}
cout<<res<<endl;
上述 \(sum_i = \sum\limits_{j=1}\limits^{i} \mu(j)\)。
标签：lfloor,frac,gcd,limits,sum,rfloor,抽象,数学,合集 From： https://www.cnblogs.com/luqyou/p/18333355