T1.P3327
知识点：莫比乌斯反演，数论分块
我们知道 \(d(ij) = \sum_{x | i}\sum_{y | j}[\gcd(x,y) == 1]\)。
所以我们就要求 \(\sum^n_{i = 1}\sum^m_{j = 1}\sum_{x | i}\sum_{y | j}[\gcd(x,y) == 1]\)。
即为 \(\sum^n_{i = 1}\sum^m_{j = 1}\lfloor \dfrac{n}{i} \rfloor \times \lfloor \dfrac{m}{j} \rfloor [\gcd(i,j) == 1]\)。
然后我们开始反演。
\[f(x) = \sum^n_{i = 1}\sum^m_{j = 1}\lfloor \dfrac{n}{i} \rfloor \times \lfloor \dfrac{m}{j} \rfloor [\gcd(i,j) == x] \]\[g(x) = \sum_{x|d} f(d) = \sum^n_{i = 1}\sum^m_{j = 1}\lfloor \dfrac{n}{i} \rfloor \times \lfloor \dfrac{m}{j} \rfloor [x | \gcd(i,j)] \]然后我们将 \(x\) 提出可得 \(g(x) = \sum^{\frac{n}{x}}_{i = 1}\sum^{\frac{m}{x}}_{j = 1}\lfloor \dfrac{n}{i \times x} \rfloor \times \lfloor \dfrac{m}{j \times x} \rfloor\)。
然后我们就考虑如何得到 \(f(1)\)。
由于莫反我们知道 \(f(x) = \sum_{i = 1}^n \mu(i) \times g(i)\)。
然后我们来考虑怎么计算 \(g(x)\)。我们可以先计算 \(s(i) = \sum^{x}_{i = 1} \lfloor \dfrac{x}{i} \rfloor\)。
然后就可以 \(O(1)\) 求出答案了。总复杂度为 \(O(t \sqrt n)\)。
标签：lfloor,gcd,dfrac,sum,rfloor,times,Record,Math From： https://www.cnblogs.com/Carousel/p/18215653