- P2568 GCD
给定 \(n\)，求：
\[\sum\limits_{p\in\mathbb{P}}\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}[\gcd(i,j)=p] \]其中 \(\mathbb{P}\) 为质数集。
推式子：
\[\begin{aligned}\sum\limits_{p\in\mathbb{P}}\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}[\gcd(i,j)=p] &= \sum\limits_{p\in\mathbb{P}}\sum\limits_{i=1}^{\lfloor\frac{n}{p}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{n}{p}\rfloor}[\gcd(i,j)=1] \\&= \sum\limits_{p\in\mathbb{P}}\Bigg(\sum\limits_{i=1}^{\lfloor\frac{n}{p}\rfloor} \Big(2\cdot \sum\limits_{j=1}^{i}[\gcd(i,j)=1]\Big) -1\Bigg) &……\dag \\&=\sum\limits_{p\in\mathbb{P}}\Bigg(\sum\limits_{i=1}^{\lfloor\frac{n}{p}\rfloor}\Big( 2\varphi(i) \Big)-1\Bigg) \end{aligned}\]\(\dag\)：感性理解，\(\lfloor\frac{n}{p}\rfloor\) 以内的互质数对对数，等于二倍的 \(i\ge j\) 的对数，减掉重复计算的 \((1,1)\) 数对。
线性筛 \(\varphi\) 并求前缀和，枚举 \(p\) 统计即可。
- P2398 GCD SUM
给定 \(n\)，求：
\[\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}\gcd(i,j) \]枚举 \(\gcd\)，枚举推式子：
\[\begin{aligned}\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}\gcd(i,j) &=\sum\limits_{d=1}^{n}\Big(d\cdot\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{n}{d}\rfloor}[\gcd(i,j)=1]\Big) \\&=\sum\limits_{d=1}^{n}\Bigg(d\cdot\Big(\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}( 2\varphi{\scriptstyle(i)} )-1\Big)\Bigg) &\text{和上一题一样的操作} \end{aligned}\]筛 \(\varphi\)，前缀和，枚举 \(d\)，搞定！
- P2522 [HAOI2011] Problem b
给定 \(1\le (a\le b,c\le d,k) \le 5\cdot 10^4\)，求：
\[\sum\limits_{i=a}^{b}\sum\limits_{j=c}^{d}[\gcd(i,j)=k] \]先通过容斥拆成四部分：记 \(A=\lceil\frac{a}{k}\rceil,B=\lfloor\frac{b}{k}\rfloor,C=\lceil\frac{c}{k}\rceil,D=\lfloor\frac{d}{k}\rfloor\)
\[\begin{aligned}&\sum\limits_{i=a}^{b}\sum\limits_{j=c}^{d}[\gcd(i,j)=k] =\sum\limits_{i=A}^{B}\sum\limits_{j=C}^{D}[\gcd(i,j)=1] \\=&\sum\limits_{i=1}^{B}\sum\limits_{j=1}^{D}[\gcd(i,j)=1]-\sum\limits_{i=1}^{B}\sum\limits_{j=1}^{C-1}[\gcd(i,j)=1]-\sum\limits_{i=1}^{A-1}\sum\limits_{j=1}^{D}[\gcd(i,j)=1]+\sum\limits_{i=1}^{A-1}\sum\limits_{j=1}^{C-1}[\gcd(i,j)=1]\end{aligned}\]记 \(f(n,m)=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}[\gcd(i,j)=1]\)，则
\(\text{原式}=f(B,D)-f(B,C-1)-f(A-1,D)+f(A-1,C-1)\)
开始推 \(f\)。
\(\begin{aligned}f(n,m)&=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}[\gcd(i,j)=1] \\ &=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\sum\limits_{d|\gcd(i,j)}\mu(d) &\text{好像是莫反的结论？} \\&=\sum\limits_{d=1}^{\min(n,m)} \Big(\mu(d) \cdot \sum\limits_{i=1}^{n}[d|i] \cdot \sum\limits_{j=1}^{m} [d|j]\Big) &\text{更换求和顺序，感性理解} \\&=\sum\limits_{d=1}^{\min(n,m)} \Big(\mu(d) \lfloor\frac{n}{d}\rfloor \lfloor\frac{m}{d}\rfloor\Big) &n\text{ 以内 }d\text{ 的倍数一共有 } \lfloor\frac{n}{d}\rfloor \text{ 个} \end{aligned}\)
最后这个式子可以数论分块求，这样这道题就做完了。
- P1829 [国家集训队] Crash的数字表格 / JZPTAB
给定 \(n,m\)，求：
\[\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\operatorname{lcm}(i,j) \]由小学奥数可知：\(\operatorname{lcm}(i,j)=\frac{ij}{\gcd(i,j)}\)，所以：
\[\begin{aligned} \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\operatorname{lcm}(i,j)&=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\frac{ij}{\gcd(i,j)} \\ &=\sum\limits_{D=1}^{min(n,m)}\Bigg(\frac{1}{D}\cdot\sum\limits_{i=1}^{\lfloor\frac{n}{D}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{D}\rfloor}\Big([\gcd(i,j)=1]ijD^2\Big)\Bigg) \\ &=\sum\limits_{D=1}^{min(n,m)}\Bigg(D\cdot\sum\limits_{i=1}^{\lfloor\frac{n}{D}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{D}\rfloor}\Big([\gcd(i,j)=1]ij\Big)\Bigg) \end{aligned}\]接下来我们化简括号内，\(D\) 之后的一部分（记为 \(f(n,m)\)）：
\[\begin{aligned} f(n,m)&=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\Big([\gcd(i,j)=1]ij\Big) \\ &=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\Big( (\sum\limits_{d|\gcd(i,j)}\mu{\scriptstyle(d)}) ij\Big) \\ &=\sum\limits_{d=1}^{\min(n,m)}\Bigg(\mu(d)\cdot \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\Big([d|i][d|j]ij\Big)\Bigg) \end{aligned}\]此式中 \(\mu(d)\) 之后的一部分，相当于这个东西：
\[\begin{aligned} &(d+2d+\ldots+\lfloor\frac{n}{d}\rfloor d)\cdot (d+2d+\ldots+\lfloor\frac{m}{d}\rfloor d) \\=&d^2\cdot (1+2+\ldots+\lfloor\frac{n}{d}\rfloor)\cdot (1+2+\ldots+\lfloor\frac{m}{d}\rfloor ) \end{aligned} \]所以：
\[f(n,m)=\sum\limits_{d=1}^{\min(n,m)}\Bigg(\mu(d)\cdot d^2\cdot\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{d}\rfloor}\Big(ij\Big)\Bigg) \]而中间那个求和符号：
\[\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{d}\rfloor}\Big(ij\Big) =\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\Big(i\cdot\sum\limits_{j=1}^{\lfloor\frac{m}{d}\rfloor}j\Big) =\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\Big(i\cdot\frac{\lfloor\frac{m}{d}\rfloor(\lfloor\frac{m}{d}\rfloor+1)}{2}\Big) =\frac{\lfloor\frac{m}{d}\rfloor(\lfloor\frac{m}{d}\rfloor+1)}{2}\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}i =\frac{\lfloor\frac{m}{d}\rfloor(\lfloor\frac{m}{d}\rfloor+1)}{2}\cdot \frac{\lfloor\frac{n}{d}\rfloor(\lfloor\frac{n}{d}\rfloor+1)}{2} \]所以：
\[f(n,m)=\sum\limits_{d=1}^{\min(n,m)}\Bigg(\mu(d)\cdot d^2\cdot\frac{\lfloor\frac{m}{d}\rfloor(\lfloor\frac{m}{d}\rfloor+1)}{2}\cdot \frac{\lfloor\frac{n}{d}\rfloor(\lfloor\frac{n}{d}\rfloor+1)}{2}\Bigg) \]\(f\) 就可以用数论分块来算。
而原式显然也可以数论分块来做，两个合二为一就能过掉此题了。
最后放一下原式最终的样子：
\[\begin{aligned} &\sum\limits_{D=1}^{min(n,m)}\Bigg(D\cdot\sum\limits_{i=1}^{\lfloor\frac{n}{D}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{D}\rfloor}\Big([\gcd(i,j)=1]ij\Big)\Bigg) =\sum\limits_{D=1}^{min(n,m)}\Bigg(D\cdot f(\lfloor\frac{n}{D}\rfloor,\lfloor\frac{m}{D}\rfloor)\Bigg) \\ =&\sum\limits_{D=1}^{min(n,m)}\Bigg(D\cdot \sum\limits_{d=1}^{\min(\lfloor\frac{n}{D}\rfloor,\lfloor\frac{m}{D}\rfloor)}\Big(\mu(d)\cdot d^2\cdot\frac{\lfloor\frac{\lfloor\frac{n}{D}\rfloor}{d}\rfloor(\lfloor\frac{\lfloor\frac{n}{D}\rfloor}{d}\rfloor+1)}{2}\cdot \frac{\lfloor\frac{\lfloor\frac{m}{D}\rfloor}{d}\rfloor(\lfloor\frac{\lfloor\frac{m}{D}\rfloor}{d}\rfloor+1)}{2}\Big)\Bigg) \end{aligned} \]- BZOJ2694. Lcm
\(\tiny\text{放的是学校OJ链接}\)
给定 \(1\le t\le 10^4\) 组 \(1\le n,m\le 4\cdot 10^6\)，求 \(i\in[1,n]\,,\,j\in[1,m]\) 且 \(\forall n,n^2 \nmid\gcd(i,j)\) 的数对 \((i,j)\) 个数，即：
\[\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\mu^2\Big(\gcd(i,j)\Big)\operatorname{lcm}(i,j) \]直接推式子，把 \(\operatorname{lcm}\) 变成 \(\gcd\)，然后枚举 \(\gcd\) ：
\[\sum\limits_{d=1}^{\min(n,m)} \mu^2(d)\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}[\gcd(i,j)=d]\frac{ij}{d} \]对 \(\operatorname{lcm}\) 的处理和上一题很像：
\[\sum\limits_{d=1}^{\min(n,m)} \mu^2(d)\cdot d\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{d}\rfloor}[\gcd(i,j)=1]ij \]这样子上一题中的 \(f\) 就出来了，省略中间一大堆推导过程：
\[\sum\limits_{d=1}^{min(n,m)}\Bigg(\mu^2(d)\cdot d \sum\limits_{k=1}^{\min(\lfloor\frac{n}{d}\rfloor,\lfloor\frac{m}{d}\rfloor)}\Big(\mu(k)\cdot k^2\cdot\frac{\lfloor\frac{n}{dk}\rfloor(\lfloor\frac{n}{dk}\rfloor+1)}{2} \cdot \frac{\lfloor\frac{m}{dk}\rfloor(\lfloor\frac{m}{dk}\rfloor+1)}{2}\Big)\Bigg) \]发现 \(kd\le\min(n,m)\)，令 \(T=kd\)，经典套路，枚举 \(T\)：\(\color{red}\tiny\text{注：在做这道题前我全然不知道这种套路}\)
\[\begin{aligned} &\sum\limits_{T=1}^{\min(n,m)} \frac{\lfloor\frac{n}{dk}\rfloor(\lfloor\frac{n}{dk}\rfloor+1)}{2} \cdot \frac{\lfloor\frac{m}{dk}\rfloor(\lfloor\frac{m}{dk}\rfloor+1)}{2} \sum\limits_{k|T}\mu(k)\cdot k^2\cdot\frac{T}{k}\cdot\mu^2(\frac{T}{k}) \\=&\sum\limits_{T=1}^{\min(n,m)} \frac{\lfloor\frac{n}{dk}\rfloor(\lfloor\frac{n}{dk}\rfloor+1)}{2} \cdot \frac{\lfloor\frac{m}{dk}\rfloor(\lfloor\frac{m}{dk}\rfloor+1)}{2} T\sum\limits_{k|T}k\cdot\mu(k)\cdot\mu^2(\frac{T}{k}) \end{aligned}\]令 \(f(k)=k\cdot \mu(k)\,,\,g(k)=\mu^2(k)\,,\,h(T)=\sum\limits_{k|T}k\cdot\mu(k)\cdot\mu^2(\frac{T}{k})\)
则 \(f,g\) 为积性函数，又 \(h=f*g\)，得 \(h\) 为积性函数。
考虑用线性筛筛出来 \(h\)，易得：
\[h(p^k)\begin{cases} 1 &k=0 \\1-p &k=1 \\-p &k=2 \\0 &k>2 \end{cases}\]这样就可以用线性筛筛出\(h\) 了。
最后对原式进行数论分块，卡卡常就过去了。
- P3327 [SDOI2015] 约数个数和
给定 \(1\le t\le 5\cdot 10^4\) 组 \(1\le n,m\le 5\cdot 10^4\)，求：
\[\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}d(ij) \]其中 \(d(n)\) 为 \(n\) 的约数个数，即 \(\sum\limits_{d|n}1\)
蒙结论，蒙出来要求的就是这个东西：
\[\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}[\gcd(i,j)=1]\lfloor\frac{n}{i}\rfloor\lfloor\frac{m}{j}\rfloor \]原理大概就是：枚举一对互质（为什么不会遗漏我也不知道）的数对 \((i,j)\)，满足 \(ab\) 存在因数 \(ij\)，且 \(a\le n\,,\,b\le m\) 的数对 \((a,b)\) 的数量显然为 \(\lfloor\frac{n}{i}\rfloor\lfloor\frac{m}{j}\rfloor\)。
但是为什么枚举互质的 \((i,j)\) 就能做到不重不漏，我也不得而知。
接下来这个东西就能做了，用莫反变一下 \([\gcd(i,j)=1]\)：
\[\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\sum\limits_{d|\gcd(i,j)}\mu(d)\lfloor\frac{n}{i}\rfloor\lfloor\frac{m}{j}\rfloor \]套路性地，把 \(d\) 提出去：
\[\sum\limits_{d=1}^{\min(n,m)}\mu(d)\Big(\sum\limits_{i=1}^{n}[d|i]\lfloor\frac{n}{i}\rfloor\Big)\Big(\sum\limits_{i=1}^{m}[d|i]\lfloor\frac{m}{i}\rfloor\Big) \]也就是：
\[\sum\limits_{d=1}^{\min(n,m)}\mu(d)\Big(\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\lfloor\frac{\lfloor\frac{n}{d}\rfloor}{i}\rfloor\Big)\Big(\sum\limits_{i=1}^{\lfloor\frac{m}{d}\rfloor}\lfloor\frac{\lfloor\frac{m}{d}\rfloor}{i}\rfloor\Big) \]我们 \(O(n\sqrt {n})\) 预处理一下 \(\sum\limits_{i=1}^{n} \Big\lfloor\dfrac{n}{i}\Big\rfloor\) ，原式最外层整除分块，这个就做完了。
附：关于此题正常一些的想法
正常情况下应该蒙出这个结论的：
\[d(nm)=\sum\limits_{i|n}\sum\limits_{j|m}[\gcd(i,j)=1] \]我们先把这个证了。
记：
\[n=\prod\limits_{i=1}^{k}p_i^{a_i} \,,\,m=\prod\limits_{i=1}^{k}p_i^{b_i}\,,\,nm=\prod\limits_{i=1}^{k}p_i^{a_i+b_i} \]对于某个质因子 \(p_i\)，我们分别考虑等式左右的取法。
对于等式左边，显然取法有 \(a_i+b_i+1\) 种。
对于等式右边，有三类取法：
\[\begin{cases} a_i &n\text{ 中 }p\text{ 取 }1\sim a_i\text{ 个，}m\text{ 中 }p\text{ 取 }0\text{ 个} \\b_i &n\text{ 中 }p\text{ 取 }0\text{ 个，}m\text{ 中 }p\text{ 取 }1\sim b_i\text{ 个} \\ 1&n\text{ 中 }p\text{ 取 }0\text{ 个，}m\text{ 中 }p\text{ 取 }0\text{ 个} \end{cases}\]加起来一共有 \(a_i+b_i+1\) 种取法。
而每个质因子都是一样的情形，所以总数相同。
有了这个结论，我们正常地推一遍式子：
\[\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\sum\limits_{x|i}\sum\limits_{y|j}[\gcd(x,y)=1] \]直接考虑更换 \(x,y\) 和 \(i,j\) 的枚举顺序：
\[\sum\limits_{x=1}^{n}\sum\limits_{y=1}^{m}\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}[x|i][y|j][\gcd(x,y)=1] \]而 \(\sum\limits_{i=1}^{n}[x|i]=\Big\lfloor\dfrac{n}{x}\Big\rfloor\)，所以原式：
\[\sum\limits_{x=1}^{n}\sum\limits_{y=1}^{m}\lfloor\dfrac{n}{x}\rfloor\lfloor\dfrac{m}{y}\rfloor[\gcd(x,y)=1] \]此时已经和我蒙出来的结论一模一样了，这就OK了。
- BZOJ3561. DZY Loves Math VI
给定 \(1 \le n,m\le 5\cdot 10^5\)，求：
\[\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\operatorname{lcm}(i,j) ^{\gcd(i,j)} \]直接推式子，枚举 \(\gcd\)：
\[\sum\limits_{d=1}^{\min(n,m)}\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{i=1}^{\lfloor\frac{m}{d}\rfloor}[\gcd(i,j)=1](ijd)^d \]\(d^d\) 提出去，莫反拆开：
\[\sum\limits_{d=1}^{\min(n,m)}d^d\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{i=1}^{\lfloor\frac{m}{d}\rfloor}\sum\limits_{k|\gcd(i,j)}\mu(k)(ij)^d \]套路地，枚举 \(k\)：
\[\sum\limits_{d=1}^{\min(n,m)}d^d \sum\limits_{k=1}^{\min(\lfloor\frac{n}{d}\rfloor,\lfloor\frac{m}{d}\rfloor)}\mu(k) \sum\limits_{i=1}^{\lfloor\frac{n}{dk}\rfloor}\sum\limits_{i=1}^{\lfloor\frac{m}{dk}\rfloor}(ik\cdot jk)^d\]\(k^{2d}\) 提出去，关于 \(i,j\) 的求和分开：
\[\sum\limits_{d=1}^{\min(n,m)}d^d \sum\limits_{k=1}^{\min(\lfloor\frac{n}{d}\rfloor,\lfloor\frac{m}{d}\rfloor)}\mu(k)\cdot k^{2d} (\sum\limits_{i=1}^{\lfloor\frac{n}{dk}\rfloor}i^d) (\sum\limits_{i=1}^{\lfloor\frac{m}{dk}\rfloor}j^d)\]本来我觉得的这个东西还能再变形，再做，于是想破脑袋想了一个上午没想出来。
但其实，我们分析分析复杂度：
\(d\) 的循环 \(O(n)\)
\(d\) 和 \(k\) 的循环是 \(\dfrac{n}{1}+\dfrac{n}{2}+\dots \dfrac{n}{n}=O(n\log n)\)
如果再算上 \(i\) 和 \(j\) 的循环，那就是 \(\dfrac{n}{1}\log(\dfrac{n}{1})+\dfrac{n}{2}\log(\dfrac{n}{2})+\dots \dfrac{n}{n}\log(\dfrac{n}{n})\)，这个东西不超过 \(O(n\log^2 n)\)，具体是多少不会算，但其实很小。
因为当 \(d\) 取了 \(d_0\) 时，最内层用到的最大的幂就是 \(\lfloor\frac{n}{d_0}\rfloor ^ d\)，于是就可以实时计算 \(1\sim \lfloor\frac{n}{d_0}\rfloor\) 的 \(d\) 次幂，如果在 \(d_0-1\) 时算过了，只需要自乘一下，否则直接用快速幂算。因为每个自然数最多算一次快速幂，这一些预处理的总复杂度就是 \(O(n\log n)\) 的。
所以直接枚举算这个式子就好了……我为什么浪费了一个上午啊啊啊啊啊啊啊啊啊啊啊啊
标签：lfloor,frac,limits,数论,Big,sum,rfloor,习题 From： https://www.cnblogs.com/baoyangawa/p/17991618