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

T4:公约数

思考难度：提高?

代码难度：省选-?

算法1：暴力计算

实际得分：10

算法2：

首先 $\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)}$gcd(i⋅j,i⋅k,j⋅k)=gcd(i,j,k)gcd(i,j)×gcd(i,k)×gcd(j,k)​

所以原式 $={\sum }_{i=1}^n{\sum }_{j=1}^m{\sum }_{k=1}^p\left({\gcd }^{}\right(i,j)+{\gcd }^{}(i,k)+gc{d}^2(j,k\left)\right)$=∑i=1n​∑j=1m​∑k=1p​(gcd2(i,j)+gcd2(i,k)+gcd2(j,k))

考虑一个式子 ${\sum }_{i=1}^n{\sum }_{j=1}^m{\gcd }^{}(i,j)={\sum }_{d=1}^{\min (n,m)}{\sum }_{x\mid d}{d}^2\mu \left(\frac{x}{d}\right)$∑i=1n​∑j=1m​gcd2(i,j)=∑d=1min(n,m)​∑x∣d​d2μ(dx​)

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

实际得分：30

算法3：

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

实际得分：50

算法4：

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

实际得分：100

算法5：

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

实际得分：100