数论出题组比赛用题：公约数

T4:公约数

思考难度：提高?

代码难度：省选-?

算法1：暴力计算

实际得分：10

算法2：

首先 $gcd⁡(i⋅j,i⋅k,j⋅k)=gcd⁡(i,j)×gcd⁡(i,k)×gcd⁡(j,k)gcd⁡(i,j,k)\gcd(i\cdot j,i\cdot k,j\cdot k)=\frac{\gcd(i,j)\times \gcd(i,k)\times \gcd(j,k)}{\gcd(i,j,k)}$

所以原式 $=∑i=1n∑j=1m∑k=1p(gcd⁡2(i,j)+gcd⁡2(i,k)+gcd2(j,k))=\sum_{i=1}^n\sum_{j=1}^m\sum_{k=1}^p(\gcd^2(i,j)+\gcd^2(i,k)+gcd^2(j,k))$

考虑一个式子 $∑i=1n∑j=1mgcd⁡2(i,j)=∑d=1min⁡(n,m)∑x∣dd2μ(xd)\sum_{i=1}^n\sum_{j=1}^m\gcd^2(i,j)=\sum_{d=1}^{\min(n,m)}\sum_{x|d}d^2\mu\left(\frac{x}{d}\right)$

考虑对后面的 $∑\sum$ 分块计算， $O(n+T⋅nn)O(n+T\cdot n\sqrt{n})$

实际得分：30

算法3：

发现前面的 $∑\sum$ 也可以分块， $O(n+T⋅n)O(n+T\cdot n)$

实际得分：50

算法4：

考虑令 $f(x)=x2,g(x)=μ(x)f(x)=x^2,g(x)=\mu\left({x}\right)$ ，计算这两个函数的狄利克雷卷积 $h (x)$ ，再对 $h (x)$ 分块计算， $O(n+T⋅n)O(n+T\cdot \sqrt{n})$

实际得分：100

算法5：

杜教筛一下，把预处理复杂度由 $O (n)$ 降低为 $O(n23)O(n^{\frac{2}{3}})$ ，~~我太懒了没有学杜教筛~~

实际得分：100