「题解」最小公倍数计数

先考虑，\(\sum_{i=1}^x \sum_{j=1}^x [ij/\gcd(i,j)\le x]\)，细节等会处理。
\(\sum_{gcd=1}^{x}\sum_{i=1}^{x/gcd}\sum_{j=1}^{x/gcd/i}[(i,j)=1]\)
其实这一步不用急着将其转化为 mu 函数，有些时候形如 \(\sum_{d=1}^x [gcd(d,x)=1]d\) 可以化成欧拉函数的形式。
\(\sum_{gcd=1}^{x}\sum_{i=1}^{x/gcd}\sum_{j=1}^{x/gcd/i}\sum_{d|gcd}\mu_d\)
\(\sum_{gcd=1}^{x}\sum_{d=1}^{x/gcd}\mu_d\sum_{i=1}^{x/gcd/d}\sum_{j=1}^{\min(x/d^2/gcd/i,x/gcd/d)} 1\)
注意原来的 \(ij/\gcd(i,j)\) 现在变成了 \(gcd*i*j*d*d\)，而不是 \(gcd*i*j*d\)（如果一步一步看下来确实是这样），其本质是 \(i,j\) 脱离 \(gcd\) 后就相当于它俩是不是互质已经不会产生影响了。（反正理解不了还是一步步看下来吧）
你会发现这个 \(\mu\) 在中间并没有什么特殊性质，然后一般见到的形式都是 \(\mu\) 在最前或最后，综合以上，我们选择将 \(\mu\) 提到最前面。
\(\sum_{d=1}^{x}\mu_d\sum_{gcd=1}^{x/d}\sum_{i=1}^{x/gcd/d}\sum_{j=1}^{\min(x/d^2/gcd/i,x/gcd/d)} 1\)
然后看着这个 \({\min(x/d^2/gcd/i,x/gcd/d)}\) 在上界处真的很不爽啊，我第一感觉是讨论（等会来看看到底可不可做）。然后使用选择将其搞下来。
\(\sum_{d=1}^{x}\mu_d\sum_{gcd=1}^{x/d}\sum_{i=1}^{x/gcd/d}\sum_{j=1}^{x/gcd/d} [gcd*i*j\leqslant x/d^2]\)
\(\sum_{d=1}^{\sqrt{x}}\mu_d\sum_{gcd=1}^{x/d^2}\sum_{i=1}^{x/gcd/d^2}\sum_{j=1}^{x/gcd/d^2} [gcd*i*j\leqslant x/d^2]\)
然后用某一场 abc（好像是 abc217C）的 trick，\(gcd,i,j\) 的地位相同，所以假设 \(gcd \leqslant i \leqslant j\)，然后 \(gcd \leqslant n^{\frac 1 3}\)，剩下的两个数直接 \(\sqrt{rest}\) 即可。然后把假设的条件去掉。
一种方法是在枚举的时候算，具体地：

LL F(LL x) {
	LL res = 0;
	for(LL i = 1; i * i * i <= x; i ++) {
		for(LL j = i + 1; j * j <= x / i; j ++) {
			res += (x / i / j - j) * 6 + 3;
		}
		res += (x / i / i - i) * 3 + 1;
	}
	return res;
}

\(x/i/j-j\) 表示 \(i\neq j \neq k\) 个数，所以乘 \(6\)，剩下的 \(i \neq j = k\) 乘 \(3\)。
\(i =j\neq k\) 乘 \(3\)，然后 \(i=j=k\) 乘 \(1\)，其实就是一个分类讨论。
还有一种方法是容斥。不展开了。
所以复杂度是 \(\mathcal {O}(不会证)\)，先去学个积分。但是注意现在我们求出来的值并不是答案。

当然还有一种方法是杜教筛。