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

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)}gcd(i⋅j,i⋅k,j⋅k)=gcd(i,j,k)gcd(i,j)×gcd(i,k)×gcd(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=1m​∑k=1p​(gcd2(i,j)+gcd2(i,k)+gcd2(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)∑i=1n​∑j=1m​gcd2(i,j)=∑d=1min(n,m)​∑x∣d​d2μ(dx​)

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

实际得分：30

算法3：

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

实际得分：50

算法4：

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

实际得分：100

算法5：

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

实际得分：100