20201201A组T3（过程推导）
[egin{equation}egin{aligned}&sum_{i=1}^{n}sum_{j=1}^{m}gcd^n(i,j)sum_{k=1}^{ij}[i ot k][j ot k]k\
&=sum_{i=1}^{n}sum_{j=1}^{m}gcd^n(i,j)varphi(ij)ij+[ij=1]\&=frac{1}{2}+frac{1}{2}sum_{i=1}^{n}sum_{j=1}^{m}gcd^n(i,j)frac{varphi(i)varphi(j)gcd(i,j)}{varphi(gcd(i,j))}ij\
&=frac{1}{2}+frac{1}{2}sum_{d=1}^{min(n,m)}frac{d^{n+1}}{varphi(d)}sum_{d|i,ile n}sum_{d|j,jle m}varphi(i)varphi(j)ij[gcd(i,j)=d]\
&这里用到了莫比乌斯反演\
&=frac{1}{2}+frac{1}{2}sum_{d=1}^{min(n,m)}frac{d^{n+1}}{varphi(d)}sum_{d|i,ile n}sum_{d|j,jle m}varphi(i)varphi(j)ijsum_{u|frac{gcd(i,j)}{d}}mu(u)\
&=frac{1}{2}+frac{1}{2}sum_{d=1}^{min(n,m)}frac{d^{n+1}}{varphi(d)}sum_{u=1}^{min(n,m)}mu(u)sum_{du|i,ile n}varphi(i)isum_{du|j,jle m}varphi(j)j\
&=frac12+frac12sum_{T=1}^{n}sum_{T|i}varphi(i)isum_{T|j}varphi(j)jsum_{d|T}frac{d^{n+1}}{varphi(d)}mu(frac{T}{d})end{aligned}end{equation}
]
注意到(sum_{i|T}varphi(i)i)是可以预处理的
同时，(sum_{d|T}frac{d^{n+1}}{varphi(d)}mu(frac{T}{d}))，可以用线筛搞定
（来自MHT）