莫比乌斯反演
1101: [POI2007]Zap
设 \(f(i)\) 表示 \((x,y)\) \(x\in [1,a],y\in [1,b]\) 满足 \(gcd(x,y)=i\) 的对数
那么答案就是 \(f(d)\)构造一个函数 \(g(i)\) 表示 \((x,y)\) \(x\in [1,a],y\in [1,b]\) 满足 \(gcd(x,y)|i\) 的对数
于是 \(g\) 与 \(f\) 满足关系式
\(g(i)=\sum\limits_{i|k}f(k)\) 满足莫比乌斯反演的第二种情况 于是套公式反演得\(f(i)=\sum\limits_{i|k}\mu(\frac {k}{i})g(k)\) 对于 \(g(i)\) 考虑 \(gcd(x,y)|i\) 即 \(x\) 与 \(y\) 都有 \(i\) 这个因子 那么 \(x\) 有 \([\frac{a}{i}]\) 个取值 \(y\) 有 \([\frac{b}{i}]\) 个取值\(g(i)=[\frac{a}{i}]\times[\frac{b}{i}]\) 于是答案\[ \begin{aligned} ans=f(d)&=\sum\limits_{d|k}\mu(\frac {k}{d})g(k)\\ &=\sum\limits_{d|k}\mu(\frac {k}{d})[\frac{a}{k}]\times[\frac{b}{k}] \end{aligned} \] 设 \(t=\frac{k}{d},k=d\times t;\)\[ \begin{aligned} ans=\sum\limits_{t=1}^{min([\frac{a}{d}],[\frac{b}{d}])}\mu(t)[\frac{\frac{a}{t}}{d}][\frac{\frac{b}{t}}{d}] \end{aligned} \] 筛一下 \(\mu(i)\) 于是就可以做到 \(O(n\times t)\) 但是效率不行呀 观察到一个形似 \(\sum\limits_{i=1}^{i\le n}[\frac{x}{i}]\) 的式子。 整除分块：(选自他人博客，但是找不到了博客地址了QAQ) 整除分块可以做到 \(O(\sqrt{n})：\)正确性证明
开始时左端点是 \(1\) 显然是没有问题的，而以后的每一次操作 \(L=R+1\)，因此，我们只需要证明每次的 \(R\) 都为正确的即可。
首先\([\frac {n}{i}]\)一定是属于该除数区间的，所以我们只需要证明该数为区间上界。反证法。设X=\([\frac {n}{i}]\)不是我们想要得到的 \(R\)，那么至少有 \(X+1\)属于答案区间。
于是有\([\frac{N}{X+1}⌋=i\)，因为是下取整，于是有\(N≥i\times (X+1)\)，于是有 \([\frac{N}{i}]≥([\frac{i×(X+1)}{i}]=X+1)\)
而根据定义有 \(X=[\frac{N}{i}]\)，于是有 \(X≥X+1\)，与事实相悖。
复杂度证明
分情况讨论。
当所选除数 \(\le \sqrt{N}\) 时，显然这一部分的除数区间个数不会超过 \(\sqrt{N}\) 个。
当所选除数\(\geq \sqrt{N}\) 时，得到的商 \(\le \sqrt{N}\)，商不超过 \(\sqrt{N}\) 种，所以除数区间也不会超过 \(\sqrt{N}\) 个。
于是总时间复杂度 \(O(\sqrt{N})\)。